Consequências de NP = PSPACE

30

Quais seriam as conseqüências desagradáveis ​​de NP = PSPACE? Estou surpreso por não ter encontrado nada sobre isso, uma vez que essas aulas estão entre as mais famosas.

Em particular, isso teria alguma conseqüência sobre as classes mais baixas?

Denis
fonte
4
Um corolário imediato, ou melhor, uma reformulação da identidade: o verificador nunca precisaria enviar uma mensagem de volta ao provador!
Alessandro Cosentino

Respostas:

28

Se , isso implicaria:NP=PSPACE

  • P#P=NP
    Ou seja, contar as soluções para um problema em seria redutível em polytime para encontrar uma solução única;NP

  • PP=NP
    Ou seja, algoritmos aleatórios em tempo polinomial com probabilidade de sucesso arbitrariamente próximos a 1/2 são reduzidos em tempo polinomial a algoritmos aleatórios em tempo polinomial com erro unilateral, onde instâncias YES são aceitas com probabilidade arbitrariamente pequena;

  • MA=NP
    Ou seja, para qualquer problema verificável em tempo polinomial, a randomização fornece, na melhor das hipóteses, uma aceleração em tempo polinomial (mas esse é apenas um corolário do colapso da hierarquia de tempo polinomial);

  • BQPNP
    Ou seja, qualquer problema solucionável por um computador quântico verifica facilmente certificados para suas respostas; isso seria um resultado positivo importante na filosofia da mecânica quântica e provavelmente seria útil no esforço de construir computadores quânticos (para verificar se eles estão fazendo o que deveriam).

Tudo isso se deve às contenções das classes do lado esquerdo no (embora também tenhamos ).B Q P P PPSPACEBQPPP

Niel de Beaudrap
fonte
11
Pode apontar para uma referência onde implica que B Q PN P . ObrigadoNP=PSPACEBQPNP
Tayfun Pay
2
@TayfunPay É basicamente quer uma referência para . A referência para isso é BV97 . No entanto, também é possível provar que B Q PP P . Veja a seguinte palestra para intuição sobre isso: scottaaronson.com/democritus/lec10.htmlBQPPSPACEBQPPP
Alessandro Cosentino
2
@AlessandroCosentino Sim, sabia que e que N PP PP S P A C E . Eu acho que eu só precisava ser apontado para agitar minha memória! Obrigado! :)BPPBQPPPPSPACENPPPPSPACE
Tayfun Pay
23

Um ponto que tem sido implicitamente, mas não explicitamente mencionado ainda é que obteríamos . Embora isso seja equivalente a P H colapsar com N P , decorre diretamente do fato de P S P A C E ser fechado sob complemento, o que é trivial de provar.NP=coNPPHNPPSPACE

Eu acho que vale a pena apontar por conta do grande número de conseqüências surpreendentes que tem: existem provas curtas que testemunham quando um gráfico não é tricolor, * não-* hamiltoniano, quando dois gráficos são * não- * isomórficos, ... e (em certo sentido de maneira mais geral) que existe algum sistema de prova de Cook-Reckhow no qual toda tautologia proposicional tem uma prova de tamanho polinomial.NP=coNP

Joshua Grochow
fonte
12

Se NP=PSPACE

1) polinomial Hierarquia entraria em colapso para .NP

2) Agora teremos pois sabemos que P S P A C EN LNPNLPSPACENL

---ATUALIZAR---

3) É sabido que a , onde eles são o espaço delimitado logarítmica versões de N P , C = P e P P respectivamente. Em seguida, por definição, nenhuma dessas classes de complexidade pode ser igual N P sob a suposição de que N P = P S P A C E .NLC=LPLNPC=PPPNPNP=PSPACE

Tayfun Pay
fonte
11
11
Observe que, se você considerar NL como a classe de idiomas que possui soluções que podem ser verificadas no espaço de log, mesmo que cada símbolo da solução seja lido no máximo uma vez (embora onde muitos logaritmicamente possam ser armazenados na fita de trabalho a qualquer momento) , o fato de ser diferente de NP indica que existe uma classe L ' que é parente de L , envolvendo Máquinas de Turing com duas fitas de entrada, mas onde uma é lida uma vez e a outra não e que é diferente de P ( onde, como há espaço polinomial na área de trabalho, as limitações de entrada de leitura única não importam).
Niel de Beaudrap
11
PLNPPLPP#LNP#L#P
11
@TayfunPay: (1) por que você não edita sua resposta para incluir os relacionamentos do seu comentário? (2) Como eles se sustentam?
Niel de Beaudrap
10

IPNP

IP=PSPACENP=PSPACE

Alex Grilo
fonte
Ainda poderia depender da implementação? Significando que ainda haveria provadores interativos que precisariam de mais trocas, apenas existem outros com apenas uma mensagem para o mesmo idioma.
Denis
Bem, isso significaria que uma mensagem é suficiente. Se entendi sua pergunta corretamente, é o mesmo para problemas em P: embora existam algoritmos de tempo polinomial para eles, ainda é possível criar um algoritmo de tempo exponencial.
Alex Grilo
2
@AlexGrilo: daí o meu comentário sob a pergunta :)
Alessandro Cosentino
@AlessandroCosentino Desculpe, eu não vi isso antes #
Alex Grilo