P = NP dans les automates cellulaires des espaces hyperboliques ?

Question

J'ai lu il y a quelques années dans ce livre que les problèmes NP sont traitables dans l'espace des automates cellulaires dans le plan hyperbolique . Qu'est-ce que ça veut dire? Est-ce P = NPd'après ces livres/articles ?

Quelques extraits du journal :

Il est bien connu que si l'on dispose « gratuitement » d'arbres binaires, il est possible de résoudre des problèmes NP en temps polynomial, voir [14, 5]. Cependant, il n'est pas immédiat d'implémenter des algorithmes d'arbres binaires dans la pentagrille, et le but de cette section est d'indiquer comment on peut procéder.

D'après ma compréhension, le problème P = NP recherche des algorithmes en temps polynomial pour résoudre des problèmes compliqués. De mon coup d'œil rapide à travers les livres et les papiers, il semble suggérer qu'il a résolu le problème. Qu'est-ce que je rate?

Voici un autre article, intitulé In Some Curved Spaces, We Can Solve NP-Hard Problems in Polynomial Time: Towards Matiyasevich's Dream .

Answer 1

Le problème P vs NP est une question sur les machines de Turing$T$, car les classes de complexité P et NP sont définies en fonction de ces machines théoriques. Appelons ces classes$P_T$et$NP_T$à partir de maintenant. L'article présente une nouvelle machine de calcul théorique$H$qui a des classes associées$P_H$(fonctionne en temps polynomial sur l'automate cellulaire hyperbolique) et$NP_H$(s'exécute en temps polynomial non déterministe sur l'automate cellulaire hyperbolique).

La première étape de cet article est une preuve que le problème 3SAT, un problème bien connu$NP_T$-problème complet, peut être résolu en temps polynomial sur cette machine, c'est à dire que ce problème réside dans$P_H$. Ensuite, ils montrent que toute réduction polynomiale en temps sur une machine de Turing peut être effectuée en temps polynomial sur leur automate hyperbolique. Étant donné que 3SAT est$NP_T$-complet, tout$NP_T$peut être réduite à une instance 3SAT en temps polynomial (sur$T$par définition, donc aussi sur$H$par leur lemme) puis être résolus en résolvant 3SAT en poly-temps, tous deux sur l'automate hyperbolique. En d'autres termes, le résultat principal de cet article (Théorème 1) peut être écrit comme$NP_T \subseteq P_H$dans notre notation. Cela ne donne pas de solution au problème P vs NP, car cela nécessiterait de relier les classes$NP_T$et$P_T$.

Notez que les auteurs incluent quelques remarques sur le problème P vs NP dans la section 4.2, où ils affirment que leur résultat est une preuve de P$\neq$NP (!):

Une troisième direction consiste en un nouvel éclairage sur la question P=NP dans les cadres ordinaires. Comme l'espace hyperbolique a des propriétés très différentes des propriétés de l'espace euclidien, en particulier, il a beaucoup plus de directions, ne serait-ce pas un indice favorable pour prouver que P$\neq$NP dans des conditions euclidiennes ? Il semble que depuis une dizaine d'années les travaux dans le domaine de la complexité inclinent à croire davantage en P$\neq$NP. Apparemment, le résultat actuel appartient également à cette tendance.