Não P = NP em Autômatos Celulares do Hiperbólica Espaços?

Question

Eu li há alguns anos atrás em este livro que Problemas NP são difíceis de ser tratados no espaço de autômatos celulares no plano hiperbólico.O que isso significa?Não P = NP de acordo com esses livros/papers?

Alguns trechos do documento:

É bem conhecido que, se temos árvores binárias à nossa disposição "de graça", é possível resolver problemas NP em tempo polinomial, ver [14, 5].No entanto, não é imediata para implementar árvore binária algoritmos no pentagrid, e o objetivo desta seção é indicar como se pode prosseguir.

No meu entendimento, o P = NP o problema é olhar para o polinômio de tempo de algoritmos para resolver problemas complicados.A partir de minha breve relance pelos livros e papéis, ele parece sugerir que ele tenha resolvido o problema.O que eu estou ausente?

Aqui é outro artigo, intitulado Em Alguns Espaços Curvos, Nós Podemos Resolver os Problemas NP-difíceis em Tempo Polinomial:Para Matiyasevich Sonho.

Answer 1

O P vs.NP problema é uma questão sobre máquinas de Turing $T$, porque as classes de complexidade P e NP são definidos em termos de esses teóricos máquinas.Vamos chamar essas classes $P_T$ e $NP_T$ a partir de agora.O documento apresenta um novo teóricos de cálculo, máquina $H$ que tem classes associadas $P_H$ (é executado em tempo polinomial no hiperbólico do autômato celular) e $NP_H$ (é executado em não-determinística em tempo polinomial no hiperbólico do autômato celular).

O primeiro passo neste papel é uma prova de que o problema 3SAT, um conhecido $NP_T$-completa problema, pode ser resolvido em tempo polinomial sobre essa máquina, por exemplo,este problema encontra-se em $P_H$.Em seguida, eles mostram qualquer redução em tempo polinomial em uma máquina de Turing pode ser realizada em tempo polinomial em seus hiperbólica autômato.Desde 3SAT é $NP_T$-completa, qualquer $NP_T$ instância pode ser reduzido a um 3SAT instância em tempo polinomial (em $T$ por definição, portanto, também no $H$ por seus lemas) e, em seguida, ser resolvido através da resolução de 3SAT na poli-tempo, tanto no plano hiperbólico autômato.Em outras palavras, o principal resultado do presente trabalho (Teorema 1) pode ser escrito como $NP_T \subseteq P_H$ na nossa notação.Isso não dá uma solução para o P vs.NP problema, uma vez que seria necessário para se relacionar com as classes $NP_T$ e $P_T$.

Nota-se que os autores incluem algumas observações sobre o P vs.NP problema na seção 4.2, onde eles afirmam que o seu resultado é a evidência P$ eq$NP (!):

Uma terceira direção consiste da nova luz lançada sobre a P=NP questão no ordinária configurações.Como o espaço hiperbólico tem propriedades que são muito diferentes das propriedades do espaço euclidiano, em particular, tem muitos mais direções, não teria que ser um indício favorável para provar que P$ eq$NP euclidiana condições?Parece que durante os últimos dez anos, os trabalhos no campo da complexidade inclinação que as pessoas acreditam mais em P$ eq$NP.Aparentemente, o presente resultado também pertence a essa tendência.