Quais seriam as consequências de PH = PSPACE?

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 . $NP=PSPACE$ $NP=coNP$ $NP\neq PSPACE$

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

cc.complexity-theory complexity-classes conditional-results Andras Farago
fonte

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

$A=B$

21414 Sylvain

@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:

entra em colapso. A problema -completo deve estar em algum nível de , que é dizer em . Uma vez que de -completo -completo (por hipótese), . $\mathsf{PH}$ $\mathsf{PSPACE}$ $\mathsf{PH}$ $\mathsf{\Sigma_k P}$ $\mathsf{PSPACE}$ $=\mathsf{PH}$ $\mathsf{PH} \subseteq \mathsf{\Sigma_k P}$

Joshua Grochow
fonte

Não é

fechada sob complemento e baixa para si? Isso é

Então, isso não implicaria

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}$

Tayfun Pay

@TayfunPay:

$\:$ Não vejo como essa implicação possa ser mostrada.

$\;\;\;\;$

@TayfunPay: Observe que o

- quando considerado como a classe única definida pela alternância de TMs polimortais com alternâncias

- também é fechado em complemento e auto-baixo (mesmo sem assumir que é igual a

)

P H

$\mathsf{PH}$

O (1)

$O(1)$

P S P A C E

$\mathsf{PSPACE}$

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.

P H

${\bf PH}$

Tayfun Pay

@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

Isso ainda implicaria grandes separações de classes de complexidade. Por exemplo, seguiria. (Se então ) $\mathrm{LOGSPACE \neq NP}$ $\mathrm{LOGSPACE = NP}$ $\mathrm{LOGSPACE = PH}$

Também implicaria por Karp-Lipton. Segue-se que tem circuitos polysize se e somente se faz. E, claro, teríamos sse . De qualquer forma, as conseqüências da solução de $\mathrm{NP \subseteq P/poly}$ $\mathrm{PSPACE = \Sigma_2 P}$ $\mathrm{NP}$ $\mathrm{PSPACE}$ $\mathrm{P = NP}$ $\mathrm{P = PSPACE}$ $\mathrm{NP}$ os problemas com eficiência seriam significativamente aumentados.

Ryan Williams
fonte

Na verdade, mesmo NL NP ≠ segue porque

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

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

Domotorp # 18/18

À medida que as respostas de salientar, ainda teria consequências significativas, embora não como os numerosos e dramáticos como . $PH=PSPACE$ $NP=PSPACE$

Rodar a questão sobre a sua cabeça, que pode ser visto como "evidência empírica" para suportar . Afinal, se , as duas declarações ( 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 é $NP\neq PH$ $NP=PH$ $PH=PSPACE$ $NP=PSPACE$ (que, por sua vez, é equivalente a ). $NP\neq PH$ $NP\neq coNP$

Andras Farago
fonte