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

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

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

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

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

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

2. Гат и Гольдвассер показали, что существует такой алгоритм для нахождения генератора , где - заданное простое число вида для простого . p2q+1$\mathbb{Z}_p^*$$p$$2q + 1$$q$

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

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

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

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

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

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

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

$2^n$$n$$2^n$

$2^{n-1}$

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

$\mathbb{F}_p$$\log p$$p$

$\log p$

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

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

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

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

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

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

$\rm{ZPP}$$\rm{RP}$$\rm{ZPP}$$\rm{NP}$$\rm{NP} \cap \rm{coNP}$

$\frac{1}{n^c}$$\text{polylog}(n)$