Löst Memcomputing wirklich ein NP-vollständiges Problem?

9

Ich stieß auf einen Artikel in Science "Memcomputing NP-vollständige Probleme in der Polynomzeit unter Verwendung von Polynomressourcen und kollektiven Zuständen" , der einige ziemlich erstaunliche Behauptungen aufstellt .

Memcomputing ist ein neuartiges Nicht-Turing- Berechnungsparadigma, bei dem interagierende Speicherzellen (kurz Memprocessors) verwendet werden, um Informationen auf derselben physischen Plattform zu speichern und zu verarbeiten. Kürzlich wurde mathematisch bewiesen, dass Memcomputing-Maschinen die gleiche Rechenleistung wie nichtdeterministische Turing-Maschinen haben . Daher können sie NP-vollständige Probleme in Polynomzeit und unter Verwendung der entsprechenden Architektur mit Ressourcen lösen, die nur mit der Eingabegröße polynomiell wachsen.

(Meins kursiv).

Ich würde dies angesichts der starken Natur der Behauptungen sofort als nicht ernst abtun, wenn es nicht die Tatsache gäbe, dass dies in Science veröffentlicht wurde und das verwandte Material einiger Autoren in Nature Physics veröffentlicht wurde. in einem IEEE-Journal und in Physics Review E , die alle seriöse, von Experten begutachtete Veröffentlichungen sind, die nicht zulassen würden, dass solche Behauptungen veröffentlicht werden, ohne dass sie ernst sind.

Also ist es wahr? Können diese Leute NP-vollständige Probleme in P-Zeit mit ihrem Modell lösen?

np-complete open-problem Alexander S König
quelle
1
Die Antwort auf die letzte Frage lautet natürlich nein. Die Definition von P hat sich nicht geändert, nur weil jemand ein ausgefallenes neues Rechenmodell erfunden hat.
Emil Jeřábek
@ EmilJeřábek sie haben nicht nur ein neues Rechenmodell erfunden, sondern auch behauptet, dass es NP entspricht.
Alexander S King
3
Sie bekommen etwas durcheinander. Wenn sie bewiesen hätten, dass ihr Modell P entspricht, würde dies bedeuten, dass P = NP ist.
Sasho Nikolov
Die Zusammenfassung des Papiers enthält die Aussage: "Es wurde kürzlich mathematisch bewiesen, dass Memcomputing-Maschinen die gleiche Rechenleistung wie nichtdeterministische Turing-Maschinen haben." Dies bedeutet nur, dass die beiden Modelle dieselben algorithmischen Probleme lösen können. Dies bedeutet nicht, dass sich Polynomzeitkomplexitäten wieder in Polynomzeitkomplexitäten niederschlagen.
Gamow
12
Siehe chat.stackexchange.com/transcript/9446/2015/12/21 , insbesondere scottaaronson.com/blog/?p=2212
Thomas Klimpel

Antworten:

9

Ich bin der Meinung, dass dies in den Kommentaren ausreichend beantwortet wurde, um alles zusammenzufassen:

  • Die Autoren behaupten nicht P = NP, was eine Aussage über deterministische und nichtdeterministische Turing-Maschinen ist.

  • Die Autoren schlagen ein Berechnungsmodell vor, von dem sie behaupten, dass es in seiner Leistung nichtdeterministischen Turing-Maschinen entspricht.

  • Die Autoren konstruieren physikalische Maschinen, die dieses Berechnungsmodell für kleine Eingabegrößen implementieren.

  • Die Autoren argumentieren, dass das Erstellen größerer Versionen mit Ressourcen in Polynomgröße physikalisch realisierbar / möglich ist.

  • Diese letzte Behauptung, die natürlich nicht bewiesen und nicht wirklich eine formale Aussage ist, würde bedeuten, dass es im Allgemeinen physikalisch möglich ist, NP-vollständige Probleme mit Ressourcen von Polynomgröße zu lösen.

  • Scott Aaronson erklärt in einem Blogbeitrag, warum diese letzte Behauptung problematisch ist und warum die Skalierbarkeit ihres Ansatzes Probleme hat: http://www.scottaaronson.com/blog/?p=2212

usul
quelle
Ich möchte darauf hinweisen, dass bis heute (Oktober 2019) kein einziger Forscher den NP-vollständigen Löser aus diesem Artikel von 2015 reproduziert hat. Darüber hinaus gab es in allen verwandten nachfolgenden Memcomputing-Artikeln derselben Autoren keine einzige Codezeile, die bei der Reproduktion des NP-vollständigen Lösers hilfreich wäre.
G. Cohen