Релятивизирует ли существование PH-полных проблем?

12

Результат Бейкера-Гилла-Соловая показал, что вопрос о P = NP не релятивизируется в том смысле, что никакое релятивизирующее доказательство (нечувствительное к присутствию оракула) не может решить вопрос о P = NP.

Мой вопрос: есть ли аналогичный результат для вопроса "Существует ли проблема полной PH?" Отрицательный ответ на этот вопрос предполагает P! = NP; утвердительный ответ был бы маловероятным, но интересным, потому что это означало бы, что PH падает до некоторого уровня.

Я не уверен, но я подозреваю, что оракул TQBF приведет к тому, что PH будет равен PSPACE, и, следовательно, будет иметь полную проблему. В дополнение к тому, что я не уверен в этом, мне любопытно, есть ли оракул, относительно которого у PH, вероятно, нет полной проблемы.

-Philip

cc.complexity-theory complexity-classes Филип Уайт
источник

16

В 1985 году Яо показал, что существуют оракулы, относительно которых полиномиальная иерархия бесконечна. По отношению к такому оракулу не существует проблем с PH-полнотой.

Кроме того, вы правы, что с оракулом TQBF PH равняется PSPACE. Фактически, даже P = PSPACE в присутствии оракула TQBF.

Srikanth
источник

Спасибо, это был первый ответ, который точно ответил на мой вопрос.

Филипп Уайт

Σ_{k} P^{A}

$\Sigma_k P^A$

A

$A$

k

$k$

A

$A$

Σ_{k} P

$\Sigma_k P$

Π_{k} P

$\Pi_k P$

14

$L$ $L \in \Sigma_k P$ $k$ $PH = \Sigma_k P$ $PH$ $PH = \Sigma_k P$ $k$ $\Sigma_k SAT$

$AC^0$ $k$ $PH$ $\Sigma_k P$

Джошуа Грохов
источник

Спасибо, этот ответ тоже полезен. Я думаю, что я знал, что у него есть полные проблемы, если он рухнет, но я ценю дополнительные детали, особенно в отношении комментария PARITY / AC0.

Филипп Уайт

Релятивизирует ли существование PH-полных проблем?

Ответы: