Apakah P = NP dalam Cellular Automata of Hyperbolic Spaces?

Aug 18 2020

Saya membaca beberapa tahun yang lalu dalam buku ini bahwa masalah NP dapat ditangani dalam ruang automata seluler di bidang hiperbolik . Apa artinya ini? Apakah P = NPmenurut buku / makalah tersebut?

Beberapa kutipan dari makalah:

Diketahui bahwa jika kita memiliki pohon biner yang kita miliki "gratis", adalah mungkin untuk memecahkan masalah NP dalam waktu polinomial, lihat [14, 5]. Namun, penerapan algoritma pohon biner dalam pentagrid tidak langsung dilakukan, dan tujuan dari bagian ini adalah untuk menunjukkan bagaimana seseorang dapat melanjutkan.

Dari pemahaman saya, masalah P = NP mencari algoritma waktu polinomial untuk menyelesaikan masalah yang rumit. Dari pandangan sepintas saya melalui buku dan kertas, sepertinya dia telah memecahkan masalah. Apa yang saya lewatkan?

Berikut adalah makalah lain, berjudul Di Beberapa Ruang Melengkung, Kita Dapat Memecahkan Masalah NP-Hard dalam Waktu Polinomial: Menuju Impian Matiyasevich .

Jawaban

7 Discretelizard Aug 18 2020 at 15:22

Masalah P vs. NP adalah pertanyaan tentang mesin Turing $T$, karena kelas kompleksitas P dan NP didefinisikan dalam istilah mesin teoritis ini. Sebut saja kelas-kelas ini$P_T$ dan $NP_T$dari sekarang. Makalah ini memperkenalkan mesin komputasi teoretis baru$H$ yang memiliki kelas terkait $P_H$ (berjalan dalam waktu polinomial pada otomat seluler hiperbolik) dan $NP_H$ (berjalan dalam waktu polinomial non-deterministik pada otomat seluler hiperbolik).

Langkah pertama dalam makalah ini adalah bukti bahwa masalah 3SAT sudah dikenal luas $NP_T$masalah -lengkap, dapat diselesaikan dalam waktu polinomial pada mesin ini, yaitu masalah ini terletak di $P_H$. Selanjutnya, mereka menunjukkan pengurangan waktu polinomial pada mesin Turing yang dapat dilakukan dalam waktu polinomial pada otomat hiperboliknya. Sejak 3SAT$NP_T$-selesai, apa saja $NP_T$ instance dapat direduksi menjadi instance 3SAT dalam waktu polinomial (aktif $T$ menurut definisi, begitu juga seterusnya $H$oleh lemma mereka) dan kemudian diselesaikan dengan memecahkan 3SAT dalam waktu-poli, keduanya pada automaton hiperbolik. Dengan kata lain, hasil utama makalah ini (Teorema 1) dapat ditulis sebagai$NP_T \subseteq P_H$dalam notasi kami. Ini tidak memberikan solusi untuk masalah P vs. NP, karena itu perlu menghubungkan kelas$NP_T$ dan $P_T$.

Perhatikan bahwa penulis memasukkan beberapa komentar tentang masalah P vs. NP di bagian 4.2, di mana mereka mengklaim hasilnya adalah bukti untuk P$\neq$NP (!):

Arah ketiga terdiri dari cahaya baru yang diberikan pada pertanyaan P = NP dalam pengaturan biasa. Karena ruang hiperbolik memiliki sifat-sifat yang sangat berbeda dari sifat-sifat ruang euclidean, khususnya, ia memiliki lebih banyak arah, bukankah itu petunjuk yang mendukung untuk membuktikan bahwa P$\neq$NP dalam kondisi euclidean? Tampaknya selama sepuluh tahun terakhir karya-karya di bidang kompleksitas membuat orang semakin percaya pada P$\neq$NP. Ternyata, hasil saat ini juga termasuk dalam tren tersebut.