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

18

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

ли нам какие-либо проблемы такие, что но ? Доказано ли его несуществование? Q B P T I M E ( n k ) Q D T I M E ( n k )QPQBPTIME(nk)QDTIME(nk)

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

aelguindy
источник
7
(1) BPP (f (n)) обычно обозначается как BPTIME (f (n)). (2) Я считаю, что в условиях сложности вычислений это открыто. (Многие примеры известны по сложности запроса и настройкам сложности связи.) (3) Если бы его несуществование уже было доказано, то мы бы уже знали, что P = BPP.
Tsuyoshi Ito
2
Кстати, в вопросе на cs.stackexchange.com у вас есть некоторое недопонимание относительно связи между BPTIME и ZPTIME, и это может быть причиной того, что вы не получили удовлетворительного ответа.
Цуёси Ито
2
@TsuyoshiIto Спасибо, я не согласен , что если мы докажем небытие , то мы знаем , , я ограничивая установку проблем в P . Возможно, B P T I M E ( n k ) P = D T I M E ( n k ) , а B P T I M E ( n k ) D T I M E ( n k)P=BPPPBPTIME(nk)P=DTIME(nk) В общем, я что-то упустил? Не могли бы выпожалуйстаточку из моего недопонимания о B P T I M E и Z P T I M E , может бытья пропустил удовлетворительный ответсамом деле ..ВпTяMЕ(NК)DTяMЕ(NК)ВпTяMЕZпTяMЕ
aelguindy
2
Ваш вопрос не говорит о том, что вы ограничиваете задачу Q тем, что находитесь внутри P. Если это ваше намерение, отредактируйте вопрос.
Tsuyoshi Ito
1
Для аппроксимации 1-медианы конечного метрического пространства с несколькими запросами к функции расстояния случайная точка дает 2-аппроксимацию в ожидании и (2 + eps) -приближение с хорошей вероятностью. Но ни один детерминированный алгоритм, который запрашивает функцию расстояния раз, не может работать лучше, чем 4-приближение. [ Чанг 2013 ]о(N2)
Нил Янг

Ответы:

10

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

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

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

Суреш Венкат
источник
Не могли бы вы дать ссылку на безусловную нижнюю границу?
T ....
1
добавлена ​​ссылка.
Суреш Венкат
13

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

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

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

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

Jagadish
источник
1
Любой детерминистический алгоритм должен выполнить не менее запросов в худшем случае . n
argentpepper
Что вы подразумеваете под «в настоящее время мы не знаем нетривиального доказательства нижней границы для любой проблемы в NP (не говоря уже о P)»?
Кристоффер Арнсфельт Хансен
Ω(nk)k>0
Ну, может быть, не для "хороших" проблем, таких как SAT; но помните, у нас есть такие нижние оценки для других задач из теорем иерархии времени. И вопрос не в «хороших» задачах, а в классах сложности.
Кристоффер Арнсфельт Хансен
Ах, верно. Я предположил, что ОП интересовали естественные проблемы. Я отредактировал свой ответ.
Джагадиш