Est-ce que 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 cela signifie?Fait P = NP d'après ces livres/articles ?

Quelques extraits du journal :

Il est bien connu que si nous disposons d’arbres binaires « gratuitement », 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 procéder.

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

Ici est un autre article, intitulé Dans certains espaces courbes, nous pouvons résoudre des problèmes NP-difficiles en temps polynomial :Vers le rêve de Matiyasevich.

Answer 1

Le P contre.Le problème 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$ désormais.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$ (fonctionne en temps polynomial non déterministe sur l'automate cellulaire hyperbolique).

La première étape de cet article est de prouver 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-à-direce problème réside dans $P_H$.Ensuite, ils montrent que toute réduction de temps polynomial sur une machine de Turing peut être effectuée en temps polynomial sur leur automate hyperbolique.Puisque 3SAT est $NP_T$-complet, n'importe lequel $NP_T$ instance 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 temps poly, tous deux sur l'automate hyperbolique.En d’autres termes, le résultat principal de cet article (théorème 1) peut s’écrire $NP_T \subseteq P_H$ dans notre notation.Cela ne donne pas de solution au problème P vs.Problème NP, car cela nécessiterait de relier les classes $NP_T$ et $P_T$.

Notez que les auteurs incluent quelques remarques sur le P vs.Problème NP dans la section 4.2, où ils prétendent que leur résultat est une preuve de P$ eq$NP (!):

Une troisième direction se compose du nouveau hangar lumineux sur la question p = np dans les contextes ordinaires.Comme l'espace hyperbolique a des propriétés très différentes de celles de l'espace euclidien, en particulier, il a beaucoup plus de directions, ne serait-ce pas un indice favorable pour prouver que P$ eq$NP dans des conditions euclidiennes ?Il semble que pendant les dix dernières années, les œuvres dans le domaine de la complexité incitent les gens à croire davantage en p$ eq$NP.Apparemment, le résultat actuel appartient également à cette tendance.