Konsekwencje NP = PSPACE

30

Jakie byłyby paskudne konsekwencje NP = PSPACE? Dziwi mnie, że nie znalazłem nic na ten temat, biorąc pod uwagę, że zajęcia te należą do najbardziej znanych.

W szczególności, czy miałoby to jakiekolwiek konsekwencje dla klas niższych?

Denis
źródło
4
Bezpośrednia konsekwencja, a raczej przeformułowanie tożsamości: weryfikator nigdy nie musiałby wysyłać wiadomości o przysłowiu!
Alessandro Cosentino

Odpowiedzi:

28

Jeżeli , oznacza to:NP=PSPACE

  • Oznacza to, że zliczanie rozwiązań problemu w N P byłoby polimeime sprowadzające się do znalezienia jednego rozwiązania;P#P=NP
    NP

  • To znaczy, że algorytmy randomizowane w czasie wielomianowym z prawdopodobieństwem sukcesu arbitralnie zbliżone do 1/2 są redukowane w czasie wielomianowym do algorytmów losowych w czasie wielomianowym z jednostronnym błędem, gdzie wystąpienia TAK są przyjmowane z arbitralnie małym prawdopodobieństwem;PP=NP

  • Oznacza to, że dla każdego problemu, który można zweryfikować w czasie wielomianowym, randomizacja zapewnia co najwyżej przyspieszenie czasu wielomianowego (ale jest to tylko następstwem załamania się hierarchii czasu wielomianowego);MA=NP

  • Oznacza to, że każdy problem rozwiązany przez komputer kwantowy łatwo weryfikuje certyfikaty pod kątem odpowiedzi; byłby to ważny pozytywny wynik w filozofii mechaniki kwantowej i prawdopodobnie byłby pomocny w wysiłku budowy komputerów kwantowych (dla weryfikacji, że robią to, co powinni).BQPNP

Wszystko to wynika z zamkniętych klas po lewej stronie w (chociaż mamy też B Q P P P ).PSPACEBQPPP

Niel de Beaudrap
źródło
1
Można wskazać na podstawie w oznacza, że B Q PN P . DziękiNP=PSPACEBQPNP
Tayfun Zapłać
2
@TayfunPay Zasadniczo chce odniesienia dla . Odniesieniem do tego jest BV97 . Jednak można również udowodnić, że B Q PP P . Zobacz następujący wykład dotyczący intuicji na ten temat: scottaaronson.com/democritus/lec10.htmlBQPPSPACEBQPPP
Alessandro Cosentino
2
@AlessandroCosentino Yes, I knew that BPPBQPPPPSPACE and that NPPPPSPACE. I guess I just needed to be pointed out to jiggle my memory! Thanks! :)
Tayfun Pay
23

One point which has been implicitly but not explicitly mentioned yet is that we would get NP=coNP. Although this is equivalent to PH collapsing to NP, it follows directly from the fact that PSPACE is closed under complement, which is trivial to prove.

Myślę, że jest warta uwagi sama z powodu dużej liczby zaskakujących konsekwencji, jakie ma: istnieją krótkie dowody świadczące o tym, że wykres nie jest trójkolorowy, * nie * hamiltonian, gdy dwa wykresy są * nie- * izomorficzne, ... i (w pewnym sensie bardziej ogólnie), że istnieje system dowodu Cook-Reckhow, w którym każda tautologia zdań ma dowód wielomianowy.NP=coNP

Joshua Grochow
źródło
12

Jeśli NP=PSPACE

1) Polynomial Hierarchy would collapse to NP.

2) We will now have that NPNL since we know that PSPACENL

---UPDATE---

3) It is known that NLC=LPL, where they are the logarithmic space bounded versions of NP, C=P and PP respectively. Then by definition none of these complexity classes could be equal NP under the assumption that NP=PSPACE.

Tayfun Pay
źródło
1
These are trivial consequences following PHPSPACE and NLPSPACE, I was hoping for more surprising consequences, for instance something between NL and P, or any new relation between two classes "strictly" below NP.
Denis
1
Note that if you consider NL as the class of languages which have solutions which can be verified in logspace, even if each symbol of the solution is read at most once (albeit where logarithmically many can be stored on the work tape at any one time), the fact that it differs from NP indicates that there is a class L' which is a relative of L, involving Turing Machines with two input tapes but where one is read-once and the other is not, and which is different from P (where because one has polynomial space on the worktape, read-once input limitations don't matter).
Niel de Beaudrap
1
@dkuper You would also have PLNP, where PL is the logarithmic space bounded version of PP as well as #LNP, where #L is the logarithmic space bounded version of #P.
Tayfun Pay
1
@TayfunPay: (1) why don't you edit your answer to include the relationships from your comment? (2) How do they hold?
Niel de Beaudrap
10

In addition to the results pointed in all other answers, there is a one involving Interactive Proof Systems (IP), that are the generalization NP where Verifier and Prover exchange messages in order to recognize a language.

It is known that IP=PSPACE, so if NP=PSPACE, it means that only one message is sufficient! For me the more impressing of this result is that the Verifier wouldn't need to challenge the Prover and can trust the very first message sent by her.

Alex Grilo
źródło
It could still depend on the implementation though? Meaning there would still be interactive provers needing more exchangse, only there exists others with only one message for the same language.
Denis
Well, it would mean that one message is sufficient. If I understood your question correctly, it's the same for problems in P: although there are polynomial time algorithms for them, one can still create an exponential time algorithm.
Alex Grilo
2
@AlexGrilo: hence my comment under the question :)
Alessandro Cosentino
@AlessandroCosentino Sorry, I didn't see it before
Alex Grilo