Apakah Memcomputing benar-benar menyelesaikan masalah NP-complete?

9

Saya menemukan sebuah artikel yang diterbitkan di Science "Memcomputing masalah NP-lengkap dalam waktu polinomial menggunakan sumber daya polinomial dan negara kolektif" , yang membuat beberapa klaim yang cukup mencengangkan.

Memcomputing adalah paradigma komputasi non-Turing baru yang menggunakan sel memori yang berinteraksi (memprocessors) untuk menyimpan dan memproses informasi pada platform fisik yang sama. Baru-baru ini terbukti secara matematis bahwa mesin memcomputing memiliki kekuatan komputasi yang sama dengan mesin Turing nondeterministic . Oleh karena itu, mereka dapat menyelesaikan masalah NP-lengkap dalam waktu polinomial dan, menggunakan arsitektur yang sesuai, dengan sumber daya yang hanya tumbuh secara polinomi dengan ukuran input.

(Milik saya cetak).

Saya akan menampik ini kelelawar sebagai tidak serius, mengingat sifat kuat dari klaim, jika bukan karena fakta bahwa ini diterbitkan dalam Science, dan bahwa materi terkait oleh beberapa penulis diterbitkan di Nature Physics , dalam jurnal IEEE dan dalam Physics Review E , yang semuanya merupakan publikasi peer-review terkemuka yang tidak akan membiarkan klaim seperti itu dipublikasikan tanpa menjadi serius.

Apakah itu benar? Bisakah orang-orang ini menyelesaikan masalah NP-complete dalam P-time menggunakan model mereka?

np-complete open-problem Alexander S King
sumber
1
Jawaban untuk pertanyaan terakhir tentu saja tidak. Definisi P tidak berubah hanya karena seseorang menemukan model perhitungan baru yang mewah.
Emil Jeřábek
@ EmilJeřábek mereka tidak hanya menciptakan model perhitungan baru, mereka juga mengklaim bahwa itu setara dengan NP.
Alexander S King
3
Anda mendapatkan sesuatu yang membingungkan. Jika mereka telah membuktikan model mereka setara dengan P, maka ini akan menyiratkan bahwa P = NP.
Sasho Nikolov
Abstrak makalah berisi pernyataan: "Baru-baru ini terbukti secara matematis bahwa mesin memcomputing memiliki kekuatan komputasi yang sama dengan mesin Turing nondeterministic." Ini hanya berarti bahwa kedua model mampu menyelesaikan masalah algoritmik yang sama. Ini tidak berarti, bahwa kompleksitas waktu polinomial diterjemahkan lagi menjadi kompleksitas waktu polinomial.
Gamow
12
Lihat chat.stackexchange.com/transcript/9446/2015/12/21 , terutama scottaaronson.com/blog/?p=2212
Thomas Klimpel

Jawaban:

9

Saya merasa ini sudah dijawab dalam komentar, jadi untuk meringkas semuanya:

  • Penulis tidak mengklaim P = NP, yang merupakan pernyataan tentang mesin Turing deterministik dan nondeterministik.

  • Para penulis mengusulkan model perhitungan yang mereka klaim untuk menunjukkan setara dalam kekuatan untuk mesin Turing nondeterministic.

  • Penulis membuat mesin fisik yang menerapkan model perhitungan ini untuk ukuran input yang kecil.

  • Para penulis berpendapat bahwa membangun versi yang lebih besar secara fisik dapat diwujudkan / dimungkinkan dengan sumber daya berukuran polinomial.

  • Klaim terakhir ini, yang tentu saja tidak terbukti dan bukan benar-benar pernyataan formal, akan menyiratkan bahwa pada umumnya dimungkinkan secara fisik untuk menyelesaikan masalah NP-complete dengan sumber daya berukuran polinomial.

  • Scott Aaronson dalam sebuah posting blog menjelaskan mengapa klaim terakhir ini bermasalah dan mengapa skalabilitas pendekatan mereka mengalami masalah: http://www.scottaaronson.com/blog/?p=2212

usul
sumber
Saya ingin mencatat bahwa pada hari ini (Oktober 2019), tidak ada satu pun peneliti yang mereproduksi pemecah NP-lengkap dari artikel 2015 ini. Selain itu, dalam semua artikel memcomputing berikutnya yang terkait oleh penulis yang sama, tidak ada satu baris kode pun yang akan membantu dalam mereproduksi pemecah NP-lengkap.
G. Cohen