Больше о PH в PP?

Недавний вопрос по Гека Bennett с просьбой , был ли класс PH содержится в классе РР, получил несколько противоречивые ответы (все это правда, кажется). С одной стороны, несколько результатов оракула были даны наоборот, а с другой Скотт предположил, что ответ, вероятно, положительный, так как теорема Тоды показывает, что PH находится в BP.PP, вероятностный вариант PP, и мы обычно считаем, что рандомизация делает не очень помогает, например, разумные предположения о твердости подразумевают PRG, которые могут заменить рандомизацию.

Теперь, в случае PP не ясно, что даже «идеальный» PRG будет означать полную дерандомизацию, поскольку естественная дерандомизация будет запускать оригинальный алгоритм с выводом PRG для всех полиномиально-многих возможных начальных чисел и займет большинство голосов. , Не ясно, что получение большинства голосов среди вычислений ПП - это то, что можно сделать в самом ПП. Тем не менее, статья Фортнау и Рейнгольда показывает, что PP закрыт при сокращении таблицы истинности (расширяя удивительный результат, что PP закрыт при пересечении), что, кажется, достаточно для получения этого большинства голосов.

Так в чем тут вопрос? Тода, Фортнау-Рейнгольд и все дерандомизации, основанные на PRG, все, похоже, релятивизируют, поэтому подразумевают, что PH в PP для каждого оракула, для которого существуют соответствующие PRG. Так что для всех оракулов , при которых PP не содержит PH (например , от Минсков и Папертого, по Beigel , или по Верещагин ), PRGS для ПП не существует. В частности, это подразумевает, что для этих оракулов в EXP нет подходящих жестких функций (в противном случае существуют NW-IW-подобные PRG). Если посмотреть на положительную сторону, это будет означать, что где-то внутри каждого из этих результатов оракула скрывается (неоднородный) PP-алгоритм для (аппроксимации) EXP с этим оракулом. Это странно, поскольку все эти результаты оракула, похоже, основаны на новых нижних границах ПП(для пороговых цепей) и прямолинейны в их машиностроении оракула, поэтому я не вижу, где скрывается верхняя граница для PP. Возможно, эта верхняя граница будет работать в целом, показывая, что (неоднородный) -PP может вычислить (или, по крайней мере, дать некоторое смещение) всего EXP? Разве что-то подобное не дало бы хотя бы симуляцию опыта EX?

Итак, я полагаю, что мой вопрос двоякий: (1) имеет ли смысл эта цепочка рассуждений? (2) Если так, то может ли кто-то «раскрыть» подразумеваемые верхние границы для PP?

Редактирование Аароном Стерлингом: подняв это на первую страницу и добавив награду. Это был один из моих любимых вопросов, и на него до сих пор нет ответов.

cc.complexity-theory counting-complexity derandomization relativization Ноам
источник

Действительно, начните с булевой функции

в AC0, которая не может быть вычислена с помощью порогового логического элемента с полилоговой (N) степенью. Для каждого оракула

определим язык

(где

- это

битов

-го среза

). Поскольку

f : {0, 1}^{N} \to {0, 1}

$f:\{0,1\}^N \rightarrow \{ 0,1\}$

A

$A$

L_{A} = {1^{n} | f (A_{n}) = 1}

$L_A= \{1^n | f(A_n)=1\}$

A_{n}

$A_n$

2^{n}

$2^n$

n

$n$

A

$A$

, для всех.

-го шага диагонализационного подберет

(для некоторого

) такихчто

'е ПП ТМА делает ошибку на

, что происходит, так как

не является полилогом (N) -пороговым (как вычисление машины PP). Таким образом

. Но, может быть,

f \in A C 0

$f \in AC0$

L_{A} \in P H^{A}

$L_A \in PH^A$

A

$A$

t

$t$

A_{n}

$A_n$

n

$n$

t

$t$

1^{n} \in L_{A} ?

$1^n \in L_A?$

f

$f$

L_{A} \notin P P^{A}

$L_A \not\in PP^A$

...

L_{A} \in P P^{A} | p o l y

$L_A \in PP^A|poly$

Ноам

Таким образом, чтобы получить также

нам нужно было бы упаковать множество экземпляров

в одну длину

. Это кажется легко выполнимым путем определения

, где для

битной строки

обозначает

-биты, описывающие, является ли

для всех

L_{A} \notin P P^{A} / p o l y

$L_A \not\in PP^A/poly$

f

$f$

n

$n$

L_{A} = {x | f (A_{x}) = 1}

$L_A = \{ x | f(A_x)=1\}$

n

$n$

x

$x$

A_{x}

$A_x$

2^{n}

$2^n$

x y \in A

$xy \in A$

возможных

длины

. Но нам нужно улучшить нижнюю границу для

чтобы требовать, чтобы

копий

в разных

разрядных строках не могли быть вычислены с помощью пороговых вентилей степени polylog (N), даже с помощью битов помощи polylog (N). Так что это должно быть ложно для любого

. Интересная верхняя граница, кажется.

2^{n}

$2^n$

y

$y$

n

$n$

f

$f$

N

$N$

f

$f$

N

$N$

f \in A C 0

$f \in AC0$

Ноам

Если подумать, то наблюдение, что под каждым оракулом, который делает PH / ⊆ PP, нет эффективных PRG, которые обманывают алгоритмы BP.PP, не должно быть более удивительным, чем тот факт, что под каждым оракулом, который делает BPP / ⊆ P, есть нет эффективных PRG, которые обманывают алгоритмы BPP. Это потому, что каждый оракул, который делает PH / ⊆ PP, также делает BP.PP / ⊆ PP по теореме Тоды (релятивизированный). Но, возможно, я упускаю суть. -

Slimton

P^{A} \neq B P P^{A}

$P^A \ne BPP^A$

B P P^{A}

$BPP^A$

P^{A} / p o l y

$P^A/poly$

P H^{A} ⊈ P P^{A}

$PH^A \not\subseteq PP^A$

P^{A}

$P^A$

P P^{A}

$PP^A$

Noam

Как я отмечал выше: в конструкциях для суть конструкции дает «неестественную» мощность BPP (и, следовательно, также P / poly), например, прививая много свидетелей для жесткого оракула в местах, где только рандомизация может найти их. Поэтому, хотя действительно интересно, что этой мощности достаточно для «общих» проблем, по крайней мере, неожиданная сила P / poly очевидна. С другой стороны, я нигде не вижу, чтобы оракул для отделения PH от PP фактически придавал неестественную силу P / poly или любому другому классу. Я не уверен, что эта разница "реальная", хотя.

P \neq B P P

$P \ne BPP$

Noam

Больше о PH в PP?

Ответы: