Quais seriam as consequências de PH = PSPACE?

13

Uma pergunta recente (veja Conseqüências de NP = PSPACE ) pediu as consequências "desagradáveis" de . As respostas listam algumas conseqüências de colapso, incluindo e outras, fornecendo muitas razões para acreditar em .N P = C O N P N P P S P A C ENP=PSPACENP=coNPNPPSPACE

Quais seriam as consequências do colapso um tanto menos dramático ?PH=PSPACE

Andras Farago
fonte
10
Eu sou a única pessoa entediada com a onda de "Consequências de " nos dias de hoje? É verdade que eles podem levar a respostas interessantes, mas a pergunta deve pelo menos exigir conseqüências inesperadas , surpreendentes etc. A=B
21414 Sylvain
2
@Sylvain: algumas dessas são realmente perguntas antigas que ressuscitaram dos mortos porque eu adicionei a tag "resultados condicionais" a elas. Você pode optar por ignorar essa tag para tornar essas perguntas menos visíveis para você.
András Salamon

Respostas:

20

entra em colapso. A P S P A C E problema -completo deve estar em algum nível de P H , que é dizer em Σ k P . Uma vez que de P S P A C E -completo = P H -completo (por hipótese), P HΣ k P .PHPSPACEPHΣkPPSPACE=PHPHΣkP

Joshua Grochow
fonte
Não é fechada sob complemento e baixa para si? Isso é P S P A C E = P S P A C E P S P A C E Então, isso não implicaria N P = C o N P e N P = P S P A C E ? PSPACEPSPACEPSPACEPSPACENP=CoNPNP=PSPACE
Tayfun Pay
@TayfunPay: Não vejo como essa implicação possa ser mostrada.
1
@TayfunPay: Observe que o - quando considerado como a classe única definida pela alternância de TMs polimortais com alternâncias O ( 1 ) - também é fechado em complemento e auto-baixo (mesmo sem assumir que é igual a P S P A C E ) PHO(1)PSPUMACE
Joshua Grochow
@ JoshuaGrochow A existência de um PH-Complete não implica que colapso? Lembro-me de algo assim no velho livro de Papadimitriou. Vou dar uma olhada hoje à noite. PH
Tayfun Pay
1
@TayfunPay: Sim, usando a mesma prova da minha resposta (mas isso não diz, e aparentemente não pode, dizer em que nível ele cai sob essa suposição).
Joshua Grochow
19

Isso ainda implicaria grandes separações de classes de complexidade. Por exemplo, seguiria. (Se L O G S P A C E = N P então L O G S P A C E = P H. )euOGSPUMACENPeuOGSPUMACE=NPeuOGSPUMACE=PH

Também implicaria P S P A C E = Σ 2 P por Karp-Lipton. Segue-se que N P tem circuitos polysize se e somente se P S P A C E faz. E, claro, teríamos P = N P sse P = P S P A C E . De qualquer forma, as conseqüências da solução de N PNPP/poeuyPSPUMACE=Σ2PNPPSPUMACEP=NPP=PSPUMACENP os problemas com eficiência seriam significativamente aumentados.

Ryan Williams
fonte
Na verdade, mesmo NL NP ≠ segue porque . NPNeuco-Neu=NP
Domotorp # 18/18
2

À medida que as respostas de salientar, ainda teria consequências significativas, embora não como os numerosos e dramáticos como N P = P S P A C E .PH=PSPUMACENP=PSPUMACE

Rodar a questão sobre a sua cabeça, que pode ser visto como "evidência empírica" para suportar . Afinal, se N P = P H , as duas declarações ( P H = P S P A C E e N P = P S P A C E ) devem ter as mesmas consequências. Como a segunda hipótese tem visivelmente mais e mais fortes consequências conhecidas, isso pode ser visto como evidência empírica para apoiar que os lados esquerdos nas equações devem ser diferentes, isto é N PNPPHNP=PHPH=PSPUMACENP=PSPUMACE (que, por sua vez, é equivalente a N P c o N P ).NPPHNPcoNP

Andras Farago
fonte