Czy Memcomputing naprawdę rozwiązuje problem NP-zupełny?

9

Zetknąłem się z artykułem opublikowanym w Science „Memcomputing NP-zupełne problemy w czasie wielomianowym z wykorzystaniem zasobów wielomianowych i stanów zbiorowych” , co czyni niektóre dość zaskakujące twierdzenia.

Memcomputing to nowy nieturingowy paradygmat obliczeń, który wykorzystuje interakcyjne komórki pamięci (w skrócie memprocessors) do przechowywania i przetwarzania informacji na tej samej platformie fizycznej. Niedawno udowodniono matematycznie, że maszyny obliczeniowe mają taką samą moc obliczeniową, co niedeterministyczne maszyny Turinga . Dlatego mogą rozwiązywać problemy NP-zupełne w czasie wielomianowym i przy użyciu odpowiedniej architektury z zasobami, które rosną wielomianowo tylko przy wielkości wejściowej.

(Moja kursywa).

Odrzuciłbym to z nietoperza jako niepoważne, biorąc pod uwagę silną naturę twierdzeń, gdyby nie fakt, że zostało to opublikowane w Science, a pokrewny materiał niektórych autorów został opublikowany w Nature Physics , w czasopiśmie IEEE oraz w Physics Review E , z których wszystkie są renomowanymi recenzowanymi publikacjami, które nie pozwoliłyby na opublikowanie takich twierdzeń bez ich poważności.

Czy to prawda? Czy osoby te mogą rozwiązać problemy z NP-kompletnością w czasie P za pomocą swojego modelu?

np-complete open-problem Alexander S. King
źródło
1
Odpowiedź na ostatnie pytanie brzmi oczywiście nie. Definicja P nie zmieniła się tylko dlatego, że ktoś wynalazł wymyślny nowy model obliczeniowy.
Emil Jeřábek
@ EmilJeřábek nie tylko wymyślili nowy model obliczeniowy, twierdzili również, że jest on równoważny NP.
Alexander S King
3
Coś się pomieszało. Gdyby udowodnili, że ich model jest równoważny P, oznaczałoby to, że P = NP.
Sasho Nikolov
Streszczenie artykułu zawiera stwierdzenie: „Ostatnio zostało matematycznie udowodnione, że maszyny obliczeniowe mają taką samą moc obliczeniową jak niedeterministyczne maszyny Turinga”. Oznacza to po prostu, że oba modele są w stanie rozwiązać te same problemy algorytmiczne. Nie oznacza to, że złożoność czasu wielomianowego ponownie przekłada się na złożoność czasu wielomianowego.
Gamow
12
Zobacz chat.stackexchange.com/transcript/9446/2015/12/21 , zwłaszcza scottaaronson.com/blog/?p=2212
Thomas Klimpel

Odpowiedzi:

9

Wydaje mi się, że odpowiedź na to pytanie jest wystarczająca w komentarzach, więc podsumowując wszystko:

  • Autorzy nie twierdzą, że P = NP jest stwierdzeniem o deterministycznych i niedeterministycznych maszynach Turinga.

  • Autorzy proponują model obliczeniowy, który, jak twierdzą, wykazuje jako równoważny z mocą niedeterministycznych maszyn Turinga.

  • Autorzy konstruują fizyczne maszyny, które implementują ten model obliczeń dla małych rozmiarów danych wejściowych.

  • Autorzy twierdzą, że budowanie większych wersji jest fizycznie możliwe do zrealizowania / możliwe przy użyciu zasobów wielkości wielomianowej.

  • To ostatnie twierdzenie, które oczywiście nie zostało udowodnione i nie jest tak naprawdę formalnym stwierdzeniem, sugerowałoby, że na ogół fizycznie możliwe jest rozwiązanie problemów NP-zupełnych z zasobami wielomianowymi.

  • Scott Aaronson w poście na blogu wyjaśnia, dlaczego to ostatnie twierdzenie jest problematyczne i dlaczego skalowalność ich podejścia ma problemy: http://www.scottaaronson.com/blog/?p=2212

usul
źródło
Chciałbym zauważyć, że na dzień dzisiejszy (październik 2019 r.) Żaden z badaczy nie odtworzył solwera NP-complete z tego artykułu z 2015 r. Co więcej, we wszystkich powiązanych artykułach memkomputerowych tych samych autorów nie było ani jednego wiersza kodu, który pomógłby w odtworzeniu solwera NP-complete.
G. Cohen