Случайность покупает нам что-нибудь внутри P?

Пусть будет классом решений задач, имеющих рандомизированный алгоритм с ограниченной двусторонней ошибкой, работающий за время . $\mathsf{BPTIME}(f(n))$ $O(f(n))$

ли нам какие-либо проблемы такие, что но ? Доказано ли его несуществование? $Q \in \mathsf{P}$ $Q \in \mathsf{BPTIME}(n^k)$ $Q \not \in \mathsf{DTIME}(n^k)$

Этот вопрос был задан на cs.SE здесь , но не получил удовлетворительного ответа.

cc.complexity-theory ds.algorithms randomized-algorithms derandomization aelguindy
источник

(1) BPP (f (n)) обычно обозначается как BPTIME (f (n)). (2) Я считаю, что в условиях сложности вычислений это открыто. (Многие примеры известны по сложности запроса и настройкам сложности связи.) (3) Если бы его несуществование уже было доказано, то мы бы уже знали, что P = BPP.

Tsuyoshi Ito

Кстати, в вопросе на cs.stackexchange.com у вас есть некоторое недопонимание относительно связи между BPTIME и ZPTIME, и это может быть причиной того, что вы не получили удовлетворительного ответа.

Цуёси Ито

@TsuyoshiIto Спасибо, я не согласен , что если мы докажем небытие , то мы знаем ,

, я ограничивая установку проблем в

. Возможно,

, а

P = B P P

$P=BPP$

P

$P$

B P T I M E (n^{k}) \cap P = D T I M E (n^{k})

$BPTIME(n^k) \cap P = DTIME(n^k)$

В общем, я что-то упустил? Не могли бы выпожалуйстаточку из моего недопонимания о

, может бытья пропустил удовлетворительный ответсамом деле ..

B P T I M E (n^{k}) \neq D T I M E (n^{k})

$BPTIME(n^k) \neq DTIME(n^k)$

B P T I M E

$BPTIME$

Z P T I M E

$ZPTIME$

aelguindy

Ваш вопрос не говорит о том, что вы ограничиваете задачу Q тем, что находитесь внутри P. Если это ваше намерение, отредактируйте вопрос.

Tsuyoshi Ito

Для аппроксимации 1-медианы конечного метрического пространства с несколькими запросами к функции расстояния случайная точка дает 2-аппроксимацию в ожидании и (2 + eps) -приближение с хорошей вероятностью. Но ни один детерминированный алгоритм, который запрашивает функцию расстояния

раз, не может работать лучше, чем 4-приближение. [ Чанг 2013 ]

o (n^{2})

$o(n^2)$

Нил Янг

Ответы:

Другим примером является оценка объема многогранника в больших размерах. Существует безусловная нижняя граница для детерминированных стратегий для приближения объема даже к экспоненциальному коэффициенту, но есть FPRAS для этой проблемы.

Обновление: соответствующий документ (ссылка на PDF ):

И. Бараны и З. Фуреди. Вычислить объем сложно, дискретная и вычислительная геометрия 2 (1987), 319-326.

Суреш Венкат
источник

Не могли бы вы дать ссылку на безусловную нижнюю границу?

T ....

добавлена ссылка.

Суреш Венкат

Проблема : Массив состоит из 1s и 0s. Найдите такое, что равно 1. $A[1..2n]$ $n$ $n$ $i$ $A[i]$

Вам разрешено запросить «Какой номер присутствует в »? Каждый запрос занимает постоянное время. $A[i]$

Решение : рандомизированный алгоритм: выберите случайный индекс и проверьте, равен ли 1. Ожидаемое количество запросов - 2, но любой детерминистический алгоритм должен выполнить не менее запросов. Следовательно, рандомизированная верхняя граница строго лучше, чем детерминированная нижняя граница в этой модели. $i$ $A[i]$ $n$

Это пример сложности запроса, на который Цуёси ссылался в комментарии.

Jagadish
источник

Любой детерминистический алгоритм должен выполнить не менее

запросов в худшем случае .

n

$n$

argentpepper

Что вы подразумеваете под «в настоящее время мы не знаем нетривиального доказательства нижней границы для любой проблемы в NP (не говоря уже о P)»?

Кристоффер Арнсфельт Хансен

Ω (n^{k})

$\Omega(n^k)$

k > 0

$k>0$

Ну, может быть, не для "хороших" проблем, таких как SAT; но помните, у нас есть такие нижние оценки для других задач из теорем иерархии времени. И вопрос не в «хороших» задачах, а в классах сложности.

Кристоффер Арнсфельт Хансен

Ах, верно. Я предположил, что ОП интересовали естественные проблемы. Я отредактировал свой ответ.

Джагадиш

$n\times n$ $\epsilon$

$O(n\log^2(n)/\epsilon^2)$

См. Также Эффективные и простые рандомизированные алгоритмы, где детерминизм сложен .

Нил Янг
источник