Каковы будут последствия PH = PSPACE?

Недавний вопрос (см Последствия NP = PSPACE ) просил для "противных" последствий . Перечисляют ответы немало последствий обрушения, в том числе и другие, обеспечивая множество причин полагать . $NP=PSPACE$ $NP=coNP$ $NP\neq PSPACE$

Какими будут последствия несколько менее драматичного коллапса ? $PH=PSPACE$

cc.complexity-theory complexity-classes conditional-results Андрас Фараго
источник

Разве я единственный человек, которому надоели всплеск вопросов "Последствия

" в эти дни? Конечно, они могут привести к интересным ответам, но вопрос должен по крайней мере вызывать неожиданные , неожиданные и т. Д. Последствия.

A = B

$A=B$

Сильвен

@Sylvain: некоторые из них на самом деле являются старыми вопросами, которые возникли из мертвых, потому что я добавил к ним тег «условные результаты». Затем вы можете игнорировать этот тег, чтобы сделать такие вопросы менее заметными для вас.

Андрас Саламон

Ответы:

рушится. -полной проблема должна быть в какомто уровне , говоримчто в . Так как это -полным -полным (по предположению), . $\mathsf{PH}$ $\mathsf{PSPACE}$ $\mathsf{PH}$ $\mathsf{\Sigma_k P}$ $\mathsf{PSPACE}$ $=\mathsf{PH}$ $\mathsf{PH} \subseteq \mathsf{\Sigma_k P}$

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

Разве

замкнут относительно комплемента и низок для себя? То есть

Так не означает ли это, что

P S P A C E

${\bf PSPACE}$

P S P A C E

${\bf PSPACE}$

{P S P A C E}^{P S P A C E}

${\bf PSPACE}^{\bf PSPACE}$

N P = C o N P

${\bf NP} = {\bf CoNP}$

N P = P S P A C E

${\bf NP} ={\bf PSPACE}$

Тайфун платят

@TayfunPay:

$\:$ Я не понимаю, как это можно показать.

$\;\;\;\;$

@TayfunPay: Note that

P H

$\mathsf{PH}$ - when considered as the single class defined by alternating poly-time TM's with

O (1)

$O(1)$ alternations - is also closed under complement and self-low (even without assuming it's equal to

P S P A C E

$\mathsf{PSPACE}$ ).

Joshua Grochow

@JoshuaGrochow Не означает ли существование PH-Complete, что

разрушается? Я помню нечто подобное в старой книге Пападимитриу. Я проверю это сегодня вечером.

P H

${\bf PH}$

Тайфун Pay

@TayfunPay: Да, используя то же доказательство, что и в моем ответе (но это не так, и, по-видимому, не может сказать, на каком уровне оно падает при таком предположении).

Джошуа Грохов

Это все еще подразумевало бы серьезное разделение классов сложности. Например, будет следовать. (Если то ) $\mathrm{LOGSPACE \neq NP}$ $\mathrm{LOGSPACE = NP}$ $\mathrm{LOGSPACE = PH}$

Also $\mathrm{NP \subseteq P/poly}$ would imply $\mathrm{PSPACE = \Sigma_2 P}$ by Karp-Lipton. It follows that $\mathrm{NP}$ has polysize circuits if and only if $\mathrm{PSPACE}$ does. And of course, we'd have $\mathrm{P = NP}$ iff $\mathrm{P = PSPACE}$ . In any case, the consequences of solving $\mathrm{NP}$ problems efficiently would be significantly increased.

Ryan Williams
источник

In fact, even NL≠NP follows because

N P^{N L \cap c o - N L} = N P

$NP^{NL\cap co-NL}=NP$ .

domotorp

As the answers point out, $PH=PSPACE$ would still have significant consequences, even though not as numerous and dramatic ones as $NP=PSPACE$ .

Turning the issue on its head, it could be viewed as "empirical evidence" to support $NP\neq PH$ . After all, if $NP=PH$ , then the two statements ( $PH=PSPACE$ and $NP=PSPACE$ ) must have the same consequences. As the second hypothesis has noticeably more and stronger known consequences, that can be viewed as empirical evidence to support that the left-hand sides in the equations must be different, that is $NP\neq PH$ (which, in turn, is equivalent to $NP\neq coNP$ ).

Andras Farago
источник