Houve mais progresso em P vs. PSPACE em comparação com P vs. NP?

7

Entendo que essa é uma pergunta um pouco vaga, mas há resultados para P vs. NP, como a questão não pode ser facilmente resolvida usando oráculos. Existem resultados como este que foram mostrados para P vs. NP, mas não foram mostrados para P vs PSPACE, de modo que há esperança de que certas técnicas de prova possam resolver P vs PSPACE, mesmo que não possam resolver P vs NP? E existem resultados não triviais que dizem que, se P = PSPACE, existem implicações que não necessariamente se aplicam a P = NP? Ou qualquer outra coisa não trivial na literatura que sugira que seja mais fácil provar P! = PSPACE do que provar P! = NP?

complexity-theory time-complexity space-complexity user2566092
fonte

parece uma pergunta justa / razoável, mas, de certa forma, todas as conjecturas abertas são igualmente difíceis ... não há realmente nenhuma maneira plausível de medir o "progresso" de qualquer conjectura ... "trabalho" em campos teóricos não é análogo ao "trabalho" em outros campos aplicados. alguns problemas têm um trabalho enorme e nenhum progresso e outros têm um trabalho pequeno, mas essencial, levando a um avanço. etc ... tem um aspecto altamente não-linear / imprevisível / assimétrica ....

vzn

Talvez isso seja mais adequado para a história.

Yuval Filmus

4

Isso realmente não responde à sua pergunta, mas há um resultado que, sob uma forma restrita de viagem no tempo (sim, viagem no tempo), sustenta que . Vou observar que o resultado não é trivial, dadas as restrições do modelo. Veja esta explicação de Scott Aaronson. $P=PSPACE$

Shaull
fonte

11

Isso é muito interessante, obrigado pelo link. Vamos ver o que acontece com a minha pergunta, mas tenho a sensação de que a resposta será um triste "Não", não estamos realmente avançando significativamente ao provar P! = PSPACE do que estamos provando P! = NP.

user2566092

4

Para provar que para um oracle "suficientemente natural" implica que deve ser muito mais fácil do que para provar . Por "suficientemente natural", estou pensando especialmente em linguagens completas para um certo nível da hierarquia polinomial. A determinação exata das condições de naturalidade faria parte da prova dessa afirmação. $\mathsf{NP}^A=\mathsf{coNP}^A$ $\mathsf{PSPACE}$ $A$ $\mathsf{NP}^A=\mathsf{PSPACE}$ $\mathsf{P}\neq\mathsf{PSPACE}$

Existem algumas razões para acreditar que esse teorema deveria existir. Já podemos provar que para alguns oracle leva ao colapso da hierarquia polinomial em . A diferença entre e na teoria descritiva da complexidade é tão pequena que é difícil imaginar como a hierarquia polinomial poderia entrar em colapso sem afetar também . Uma razão mais sutil para acreditar nisso, que também sugere uma estratégia para uma prova, é que é fechado sob interseções finitas e uniões quase arbitrárias (= limitadas pelo PSPACE). $\mathsf{NP}^A=\mathsf{coNP}^A$ $\mathsf{PH}$ $A$ $\mathsf{PH}=\mathsf{NP}^A$ $\mathsf{PH}$ $\mathsf{PSPACE}$ $\mathsf{PSPACE}$ $\mathsf{NP}^A$

Thomas Klimpel
fonte

Sei que essa é uma resposta problemática em certos aspectos, mas deve explicar por que realmente não esperamos que seja muito mais fácil de provar do que .

P \neq P S P A C E

$\mathsf{P}\neq\mathsf{PSPACE}$

P \neq N P

$\mathsf{P}\neq\mathsf{NP}$

Thomas Klimpel

Como nota de cautela, temos o seguinte teorema: "Existe , de modo que Em geral, para cada existe um oráculo, em relação ao qual a hierarquia polinomial possui exatamente níveis ".

A \subseteq {0, 1}^{*}

$A \subseteq \{0, 1\}^∗$

{P H}^{A} \neq {P S P A C E}^{A}

$\mathsf{PH}^A \neq \mathsf{PSPACE}^A$

k

$k$

k

$k$

Thomas Klimpel

Houve mais progresso em P vs. PSPACE em comparação com P vs. NP?

Respostas: