Рандомизированный алгоритм, который «выглядит» детерминированным?

31

Существует ли интересный пример рандомизированного алгоритма для задачи поиска, который всегда выводит один и тот же (правильный) ответ, независимо от его внутренней случайности, но который использует случайность так, что его ожидаемое время выполнения лучше, чем время выполнения самого быстрого из известных детерминированный алгоритм для задачи?

В частности, мне было интересно, существует ли такой алгоритм для нахождения простого числа между n и 2n. Там нет известного полиномиального времени детерминированного алгоритма. Существует тривиальный рандомизированный алгоритм, который работает просто путем выборки случайных целых чисел в интервале, который работает благодаря теореме о простом числе . Но существует ли алгоритм вышеупомянутого вида, чье ожидаемое время работы является промежуточным между двумя?

РЕДАКТИРОВАТЬ: Чтобы немного уточнить мой вопрос, я хотел такой алгоритм для задачи, где есть много возможных правильных выходных данных, и все же случайный алгоритм основывается на одном, независимо от его случайности. Я понимаю, что вопрос, вероятно, не полностью уточнен ...

Арнаб
источник
3
Чтобы дать вам некоторые ключевые слова для поиска, рандомизированные алгоритмы, которые всегда дают правильный ответ (и использует случайность для более короткого времени выполнения), называются алгоритмами Лас-Вегаса (в отличие от алгоритмов Монте-Карло) или алгоритмами с нулевой ошибкой, а связанный класс сложности - ZPP. ,
Tsuyoshi Ito
@Tsuyoshi: Спасибо за ваш комментарий. Но я не знаю алгоритмов типа Лас-Вегаса для задач поиска. Это мой вопрос
Арнаб
Если есть рандомизированный алгоритм для поиска уникальных равновесий Нэша, который бы ответил на ваш вопрос.
Уоррен Шуди
Возможно, есть какая-то проблема, связанная с атаками на день рождения ( en.wikipedia.org/wiki/Birthday_attack ), которая соответствует вашим требованиям?
Уоррен Шуди

Ответы:

23

Шафи Голдвассер сообщила мне, что она и соавторы исследуют именно такие алгоритмы для теоретико-числовых задач! Известно следующее:

  1. Ленстра показала, что существует такой алгоритм для нахождения квадратичного не вычетов по модулю заданного простого числа.

  2. Гат и Гольдвассер показали, что существует такой алгоритм для нахождения генератора , где - заданное простое число вида для простого . p2q+1qZpp2q+1q

(Я не знаю о цитируемых ссылках.) Также продолжается исследование вопроса, который я задал, о поиске простого числа между и .2 nn2n

РЕДАКТИРОВАТЬ: статья Гат и Голдвассер в настоящее время публикуется: http://eccc.hpi-web.de/report/2011/136/ . Эта статья, однако, не решает вопрос о поиске простого числа между и .2 nn2n

оборота арнаб
источник
1
Виртуальный +1. Это действительно интересно, буду высматривать бумаги.
Андрас Саламон
2
Несмотря на примечание, я проголосовал за этот ответ просто потому, что это хороший ответ. Я не думаю, что есть что-то плохое в том, чтобы выслать хороший ответ для кого-то другого. Я начал обсуждение Meta по этому поводу.
Цуёси Ито
1
Я удалил примечание и сделал его "сообществом вики" согласно обсуждению в мета-ветке.
Арнаб
Мета-поток, упомянутый arnab, можно найти здесь: meta.cstheory.stackexchange.com/q/607/873 .
MS Dousti
18

Подсчитывают ли рандомизированные структуры данных?

Есть список пропусков, который представляет собой отсортированную ассоциативную структуру данных карты.

Время выполнения обычных операций, таких как вставка, извлечение и удаление, находится (в ожидаемом случае) на одном уровне с операциями в сбалансированных деревьях поиска - то есть . Однако иногда считается, что структура данных имеет гораздо лучший постоянный коэффициент, чем реализация дерева поиска, если все сделано правильно (это критически зависит от хорошего и эффективного источника случайности). Лучший постоянный коэффициент, вероятно, является следствием того, что не нужно выполнять перебалансировку (или любую аналогичную операцию).O(logn)

Конрад Рудольф
источник
Благодарность! Это определенно имеет значение и является нетривиальным ответом на мой оригинальный вопрос. Я хотел проблему, хотя и более похожую на проблему первопричины, где есть много потенциальных решений.
Арнаб
Добавьте списки переходов к этому ходу мыслей.
Рафаэль
13

Как насчет рандомизированного симплексного алгоритма полиномиального времени Келнера и Спилмана? Находит оптимальную вершину линейной программы. Не существует детерминированного симплексного алгоритма, который, как было доказано, работает за полиномиальное время, и для многих из них могут быть построены патологические примеры, которые заставляют алгоритм занимать экспоненциальное время.

Конечно, существуют алгоритмы внутренних точек полиномиального времени, так что это не совсем то, что вы ищете.

Питер Шор
источник
Если есть несколько оптимальных точек, будет ли Келнер-Шпильман всегда возвращать одну и ту же точку?
Сашо Николов
3
Обычные линейные программы имеют только одну оптимальную точку, поэтому, используя возмущение, можно создать вариант Келнера-Шпильмана, который всегда возвращает одну и ту же оптимальную точку.
Питер Шор
12

2nn2n

2n1

Это подходит?

Андраш Саламон
источник
Ницца!! Это определенно подходит, хотя я искал более нетривиальный пример, где улучшение во время выполнения более существенное.
Арнаб
Вам не нужна древовидная структура, это работает с массивом.
sdcvvc
7

Fplogpp

logp

Srikanth
источник
6

Был проект «Полимат», посвященный смежному вопросу: http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

Энтони Леверье
источник
Да, это послужило источником мотивации для моего вопроса. Я не думаю, что они явно упомянули этот вопрос в проекте Polymath.
Арнаб
3

Что касается вашего первого вопроса, я сначала подумал о быстрой сортировке, но это должно быть очевидно.

Существует алгоритм сопоставления строк ( Nebel, 2006 ), который использует вероятностные идеи. Однако я знаю, что это самый быстрый из существующих подходов, и вам, очевидно, нужны некоторые образцы для обучения.

Рафаэль
источник
Медиана также быстрее, но не так резко.
Арам Харроу
3

Следующая статья STACS '97 может быть интересна для вашего случая: Сложность генерации тестовых экземпляров .

Аннотация: Недавно Ватанабе предложил новую платформу для проверки правильности и поведения в среднем случае алгоритмов, которые направлены на эффективное решение данной задачи поиска NP в среднем. Идея состоит в том, чтобы случайным образом генерировать сертифицированные экземпляры способом, который напоминает базовое распределение. Мы обсуждаем этот подход и показываем, что тестовые экземпляры могут быть созданы для каждой проблемы поиска NP с неадаптивными запросами к оракулу NP. Кроме того, мы представляем типы генераторов тестовых экземпляров в Лас-Вегасе и Монте-Карло и показываем, что эти генераторы можно использовать для определения правильности и эффективности алгоритма в среднем. На самом деле, нетрудно построить генераторы Монте-Карло для всех задач поиска RP, а также генераторы Лас-Вегаса для всех задач поиска ZPP. С другой стороны,

В частности, посмотрите на страницу 384 под следствием 12:

ZPPRPZPPNPNPcoNP

М.С. Дусти
источник
2

1ncpolylog(n)

Ramprasad
источник
3
Это относится к тестированию, а не к поиску ...
Дана Мошковиц
Меня больше интересовали проблемы поиска. Для решения проблем существуют алгоритмы Лас-Вегаса.
Арнаб