Será que P = NP em Autômatos Celulares de Espaços Hiperbólicos?

Question

Li há alguns anos neste livro que problemas NP são tratáveis ​​no espaço de autômatos celulares no plano hiperbólico . O que isto significa? Será que P = NPde acordo com esses livros/papéis?

Alguns trechos do jornal:

É bem conhecido que se tivermos árvores binárias à nossa disposição “de graça”, é possível resolver problemas NP em tempo polinomial, veja [14, 5]. No entanto, não é imediato implementar algoritmos de árvore binária no pentagrid, e o objetivo desta seção é indicar como proceder.

Pelo que entendi, o problema P = NP está procurando algoritmos de tempo polinomial para resolver problemas complicados. Do meu olhar superficial pelos livros e papéis, parece sugerir que ele resolveu o problema. o que estou perdendo?

Aqui está outro artigo, intitulado In Some Curved Spaces, We Can Solve NP-Hard Problems in Polynomial Time: Towards Matiyasevich's Dream .

Answer 1

O problema P vs. NP é uma questão sobre máquinas de Turing$T$, porque as classes de complexidade P e NP são definidas em termos dessas máquinas teóricas. Vamos chamar essas classes$P_T$e$NP_T$de agora em diante. O artigo apresenta uma nova máquina de computação teórica$H$que tem classes associadas$P_H$(roda em tempo polinomial no autômato celular hiperbólico) e$NP_H$(roda em tempo polinomial não determinístico no autômato celular hiperbólico).

O primeiro passo neste artigo é uma prova de que o problema 3SAT, um problema bem conhecido$NP_T$-problema completo, pode ser resolvido em tempo polinomial nesta máquina, ou seja, este problema está em$P_H$. Em seguida, eles mostram que qualquer redução de tempo polinomial em uma máquina de Turing pode ser realizada em tempo polinomial em seu autômato hiperbólico. Como o 3SAT é$NP_T$-completo, qualquer$NP_T$instância pode ser reduzida a uma instância 3SAT em tempo polinomial (em$T$por definição, assim também em$H$pelo seu lema) e então ser resolvido resolvendo 3SAT em poli-tempo, ambos no autômato hiperbólico. Em outras palavras, o principal resultado deste artigo (Teorema 1) pode ser escrito como$NP_T \subseteq P_H$em nossa notação. Isso não dá uma solução para o problema P vs. NP, porque isso precisaria relacionar as classes$NP_T$e$P_T$.

Observe que os autores incluem algumas observações sobre o problema P vs. NP na seção 4.2, onde afirmam que seu resultado é evidência para P$\neq$NP (!):

Uma terceira direção consiste na nova luz lançada sobre a questão P=NP nos ambientes comuns. Como o espaço hiperbólico tem propriedades muito diferentes das propriedades do espaço euclidiano, em particular, tem muito mais direções, isso não seria uma dica favorável para provar que P$\neq$NP em condições euclidianas? Parece que nos últimos dez anos os trabalhos no campo da complexidade levam as pessoas a acreditar mais em P$\neq$NP. Aparentemente, o presente resultado também pertence a essa tendência.