Иерархия для BPP против дерандомизации

29

В одном предложении: подразумевает ли существование иерархии для какие-либо результаты дерандомизации?BPTIME

но неопределенный вопрос: подразумевает ли существование иерархии для какие-либо трудные нижние границы? Влияет ли решение этой проблемы на известный барьер в теории сложности?BPTIME

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

Немного предыстории : содержит те языки, членство которых может быть определено вероятностным токарным станком за время f ( n ) с ограниченной вероятностью ошибки. Точнее говоря, язык L B P T I M E ( f ( n ) ), если существует вероятностная машина Тьюринга T такая, что для любого x L машина T работает за время O ( f ( | x | )BPTIME(f(n))f(n)LBPTIME(f(n))TxLT И принимает с вероятностьюпо меньшей мере 2 / 3 , и для любого х L , Т пробегает по времени O ( F ( | х | ) ) и отклоняет с вероятностьюпо меньшей мере 2 / 3 .O(f(|x|))2/3xLTO(f(|x|))2/3

Безусловно, открыто, является ли для всех c > 1 . Барак показал, что существует строгая иерархия для B P T I M E для машин с O ( log n )BPTIME(nc)BPTIME(n)c>1BPTIMEO(logn)совет. Fortnow и Santhanam улучшили это до 1 совета. Это заставляет меня думать, что доказательство существования вероятностной иерархии времени не так уж далеко. С другой стороны, результат все еще открыт, и я не могу найти никакого прогресса после 2004 года. Ссылки, как обычно, можно найти в зоопарке .

Отношение к дерандомизации исходит из результатов Импальяццо и Вигдерсона: они показали, что в предположении вероятной сложности для любой константы d и некоторой константы c . Согласно классическим теоремам иерархии времени для детерминированного времени, это подразумевает иерархию времени для вероятностного времени. Я задаю обратный вопрос: вероятностный высокоуровневый удар по барьеру, связанному с доказательством результатов дерандомизации?BPTIME(nd)DTIME(nc)dc


РЕДАКТИРОВАТЬ: Я принимаю ответ Райана как более полное решение.

Если у кого-то есть наблюдения о том, что стоит между нами и доказывает существование иерархии для вероятностного времени, не стесняйтесь отвечать / комментировать. Конечно, очевидный ответ заключается в том, что имеет семантическое определение, которое не поддается классическим методам. Меня интересуют менее очевидные наблюдения.BPTIME

Сашо Николов
источник

Ответы:

22

Пусть PTH будет гипотезой, что существует вероятностная иерархия времени. Предположим, что ответ на ваш вопрос верный, т. Е. «PTH подразумевает » для некоторого фиксированного c . Тогда E X P B P P будет безусловно верным. Рассмотрим два случая:BPPTIME[2nc]cEXPBPP

  • Если РТН ложно, то . Это противоположно тому, что заметил Ланс.EXPBPP
  • Если РТН истинно, то "РТН означает " , так что снова Е Х Р Б Р P .BPPTIME[2nc]EXPBPP

EXPBPPEXPBPP

Райан Уильямс
источник
3
Ницца. Таким образом, существует серьезный барьер для того, чтобы показать, что существует барьер, связанный с дерандомизацией, для доказательства ПТГ.
Сашо Николов
18

Нетрудно вывести вероятностную иерархию времени, если BPP = EXP, крайний случай отсутствия дерандомизации.

Лэнс Фортноу
источник
2
И вам не нужен BPP = EXP, вам просто нужен BPP, а не DTIME (2 ^ {n ^ c)}) для константы c> 1. То есть вам нужно только, чтобы BPP был сложным для DTIME, а не этот BPP может решить электронные языки. Это говорит о том, что крайнее отсутствие дерандомизации подразумевает иерархию. Как насчет промежуточного отсутствия дерандомизации?
Джефф Кинн
Хорошие наблюдения. Таким образом, падение вверх так же хорошо, как падение вниз, чтобы установить иерархию. Это подрывает мою мотивацию, но, технически говоря, все еще возможно, что вероятностная иерархия подразумевает дерандомизацию, даже если отсутствие дерандомизации подразумевает вероятностную иерархию (ложное утверждение может подразумевать истинное утверждение)? Неясный вопрос о том, какие барьеры преодолевает проблема иерархии БПП, остается в силе. Например, возможно, что BPP имеет иерархию для всех оракулов (неразрешенный вопрос Fortnow-Sipser'89), поэтому релятивизация не является проблемой на заднем плане?
Сашо Николов