Supondo que P! = NP, acredito que tenha sido demonstrado que existem problemas que não estão em P e nem em NP-Complete. O isomorfismo do gráfico é conjecturado como um problema.
Existe alguma evidência de mais dessas "camadas" no NP? isto é, uma hierarquia de mais de três classes começando em P e culminando em PN, de modo que cada uma seja um superconjunto apropriado da outra?
É possível que a hierarquia seja infinita?
cc.complexity-theory
Aryabhata
fonte
fonte
Respostas:
Sim! De fato, existe comprovadamente uma hierarquia infinita de problemas cada vez mais difíceis entre P e NP-completo sob a suposição de que P! = NP. Este é um corolário direto da prova do Teorema de Ladner (que estabeleceu o não-vazio de NP \ P)
Formalmente, sabemos que para cada conjunto S que não está em P, existe S 'não em P, de modo que S' é redutor de Karp em S, mas S não é redutor de Cook em S '. Portanto, se P! = NP, existe uma sequência infinita de conjuntos S 1 , S 2 ... em NP \ P, de modo que S i + 1 é Karp-redutível a S i, mas S i não é Cook-redutível a S i + 1 .
É certo que a esmagadora maioria desses problemas é de natureza altamente artificial.
fonte
Existe uma noção de "não determinismo limitado" que limita os bits não determinísticos exigidos pela máquina de Turing para chegar a uma solução. A classe NP requer, por exemplo, O (n) bits. Ao limitar os bits não determinísticos ao polilog, define uma hierarquia infinita de classes de complexidade denominada hierarquia \ beta P, todas com problemas completos.
Veja, por exemplo, o seguinte artigo para obter detalhes: Goldsmith, Levy, Mundhenk, "Limited nondeterminism", SIGACT News, vol. 27 (2), páginas 20-29, 1996.
fonte