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

13

Недавний вопрос (см Последствия NP = PSPACE ) просил для "противных" последствий . Перечисляют ответы немало последствий обрушения, в том числе N P = C O N P и другие, обеспечивая множество причин полагать N P P S P A C E .NP=PSPACENP=coNPNPPSPACE

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

Андрас Фараго
источник
10
Разве я единственный человек, которому надоели всплеск вопросов "Последствия " в эти дни? Конечно, они могут привести к интересным ответам, но вопрос должен по крайней мере вызывать неожиданные , неожиданные и т. Д. Последствия. A=B
Сильвен
2
@Sylvain: некоторые из них на самом деле являются старыми вопросами, которые возникли из мертвых, потому что я добавил к ним тег «условные результаты». Затем вы можете игнорировать этот тег, чтобы сделать такие вопросы менее заметными для вас.
Андрас Саламон

Ответы:

20

рушится. P S P C E -полной проблема должна быть в какомто уровне P H , говоримчто в Е К Р . Так как это Р С Р С Е -полным = Р Н -полным (по предположению), Р НЕ к Р .PHPSPACEPHΣkPPSPACE=PHPHΣkP

Джошуа Грохов
источник
Разве замкнут относительно комплемента и низок для себя? То есть P S P A C E = P S P A C E P S P A C E Так не означает ли это, что N P = C o N P и N P = P S P A C E ? PSPACEPSPACEPSPACEPSPACENP=CoNPNP=PSPACE
Тайфун платят
@TayfunPay: Я не понимаю, как это можно показать.
1
@TayfunPay: Note that PH - when considered as the single class defined by alternating poly-time TM's with O(1) alternations - is also closed under complement and self-low (even without assuming it's equal to PSPACE).
Joshua Grochow
@JoshuaGrochow Не означает ли существование PH-Complete, что разрушается? Я помню нечто подобное в старой книге Пападимитриу. Я проверю это сегодня вечером. PH
Тайфун Pay
1
@TayfunPay: Да, используя то же доказательство, что и в моем ответе (но это не так, и, по-видимому, не может сказать, на каком уровне оно падает при таком предположении).
Джошуа Грохов
19

Это все еще подразумевало бы серьезное разделение классов сложности. Например, будет следовать. (Если L O G S P A C E = N P, то L O G S P A C E = P H. )LOGSPACENPLOGSPACE=NPLOGSPACE=PH

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

Ryan Williams
источник
In fact, even NL≠NP follows because NPNLcoNL=NP.
domotorp
2

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 NPPH. 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 NPPH (which, in turn, is equivalent to NPcoNP).

Andras Farago
источник