Memcomputing résout-il vraiment un problème NP-complet?

9

Je suis tombé sur un article publié dans Science "Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states" , qui fait des affirmations assez étonnantes.

Memcomputing est un nouveau paradigme de calcul non-Turing qui utilise des cellules de mémoire en interaction (memprocessors pour faire court) pour stocker et traiter des informations sur la même plate-forme physique. Il a été récemment prouvé mathématiquement que les machines de memcomputing ont la même puissance de calcul que les machines de Turing non déterministes . Par conséquent, ils peuvent résoudre des problèmes NP-complets en temps polynomial et, en utilisant l'architecture appropriée, avec des ressources qui ne croissent que polynomialement avec la taille d'entrée.

(Le mien en italique).

Je rejetterais cette affirmation comme étant non grave, étant donné la nature forte des affirmations, si ce n'était du fait que cela a été publié dans Science et que le matériel connexe de certains des auteurs a été publié dans Nature Physics , dans une revue de l'IEEE et dans Physics Review E , qui sont toutes des publications réputées évaluées par des pairs qui ne permettraient pas que de telles allégations soient publiées sans qu'elles soient sérieuses.

Est-ce que c'est vrai? Ces personnes peuvent-elles résoudre des problèmes NP-complets en temps P en utilisant leur modèle?

np-complete open-problem Alexander S King
la source
1
La réponse à la dernière question est bien sûr non. La définition de P n'a pas changé simplement parce que quelqu'un a inventé un nouveau modèle de calcul sophistiqué.
Emil Jeřábek
@ EmilJeřábek ils n'ont pas seulement inventé un nouveau modèle de calcul, ils ont également affirmé qu'il était équivalent à NP.
Alexander S King
3
Vous mélangez quelque chose. S'ils avaient prouvé que leur modèle était équivalent à P, cela impliquerait que P = NP.
Sasho Nikolov
Le résumé de l'article contient la déclaration: "Il a été récemment prouvé mathématiquement que les machines de memcomputing ont la même puissance de calcul que les machines de Turing non déterministes." Cela signifie simplement que les deux modèles sont capables de résoudre les mêmes problèmes algorithmiques. Cela ne signifie pas que les complexités temporelles polynomiales se traduisent à nouveau en complexités temporelles polynomiales.
Gamow
12
Voir chat.stackexchange.com/transcript/9446/2015/12/21 , en particulier scottaaronson.com/blog/?p=2212
Thomas Klimpel

Réponses:

9

Je pense que cela a été suffisamment répondu dans les commentaires, donc pour résumer le tout:

  • Les auteurs ne prétendent pas P = NP, qui est une déclaration sur les machines de Turing déterministes et non déterministes.

  • Les auteurs proposent un modèle de calcul qu'ils prétendent montrer est équivalent en puissance aux machines de Turing non déterministes.

  • Les auteurs construisent des machines physiques qui implémentent ce modèle de calcul pour de petites tailles d'entrée.

  • Les auteurs soutiennent que la construction de versions plus grandes est physiquement réalisable / possible avec des ressources de taille polynomiale.

  • Cette dernière affirmation, qui n'est bien sûr pas prouvée et n'est pas vraiment une déclaration formelle, impliquerait qu'il est généralement physiquement possible de résoudre des problèmes NP-complets avec des ressources de taille polynomiale.

  • Scott Aaronson dans un article de blog explique pourquoi cette dernière affirmation est problématique et pourquoi l'évolutivité de leur approche a des problèmes: http://www.scottaaronson.com/blog/?p=2212

usul
la source
Je voudrais noter qu'à compter d'aujourd'hui (octobre 2019), aucun chercheur n'a reproduit le solveur NP-complet de cet article de 2015. De plus, dans tous les articles ultérieurs sur le memcomputing des mêmes auteurs, il n'y avait pas une seule ligne de code qui aiderait à reproduire le solveur NP-complete.
G. Cohen