Kandidat alami melawan dugaan Isomorfisme?

18

Yang terkenal isomorfisma dugaan dari Berman dan Hartmanis mengatakan bahwa semua bahasa -Lengkap adalah waktu polinomial isomorfik (p-isomorfik) satu sama lain. Pentingnya kunci dari dugaan adalah bahwa hal itu menyiratkan P N P . Itu diterbitkan pada tahun 1977, dan sepotong bukti pendukung adalah bahwa semua N P masalah -Lengkap diketahui pada saat itu memang p-isomorfik. Faktanya, mereka semua dapat didayung , yang merupakan sifat alami yang bagus, dan menyiratkan p-isomorfisme dengan cara nontrivial.NPPNPNP

Sejak itu, kepercayaan pada dugaan itu memburuk, karena kandidat -lengkap bahasa telah ditemukan yang tidak mungkin p-isomorfik untuk S A T , meskipun masalahnya masih terbuka. Sejauh yang saya tahu, bagaimanapun, tidak satupun dari kandidat ini mewakili masalah alami ; mereka dibangun melalui diagonalisasi untuk tujuan menyangkal dugaan Isomorfisme.NPSAT

Apakah masih benar, setelah hampir empat dekade, yang semua alami yang dikenal masalah -Lengkap adalah p-isomorfik ke S A T ? Atau, adakah yang diduga kandidat alami yang bertentangan?NPSAT

Andras Farago
sumber
2
Saya akan menahan diri dari downvoting, tetapi saya pribadi terhadap semua pertanyaan yang meminta adanya sesuatu yang "alami" tanpa mendefinisikan apa yang alami. Saya tidak mengatakan saya menentang semua gagasan "kabur", tetapi saya pikir alam terlalu luas dan beberapa sifat yang diinginkan / tidak diinginkan yang lebih konkrit harus ditentukan lebih lanjut.
Sasho Nikolov
2
+1 pertanyaan yang bagus. @SashoNikolov, sebelum penemuan mesin Turing, definisi formal dari algoritma, gagasan intuitif telah dikenal dan telah digunakan selama ribuan tahun. Kurangnya definisi formal tentang masalah alam seharusnya tidak menghalangi kita untuk menggunakannya secara informal. Masalah alam adalah konsep yang Anda tahu ketika Anda melihatnya.
Mohammad Al-Turkistany
4
Saya setuju dengan Mohammad bahwa Anda biasanya tahu masalah alami ketika Anda melihatnya. Namun, "alami" juga tergantung pada konteksnya, dan dalam beberapa konteks ada gagasan yang lebih jelas - atau mungkin hanya serangkaian contoh alamiah yang lebih disepakati dengan baik - dari yang lain. Saya pikir masalah khusus kasus ini (NP-complete) termasuk dalam kelas sebelumnya. Misalnya, menerapkan fungsi satu arah ke SAT untuk mendapatkan masalah NP-lengkap lainnya (ide dasar di balik beberapa kandidat yang melanggar Berman-Hartmanis) jelas menghasilkan masalah "tidak wajar".
Joshua Grochow
4
Masalah dengan 'alami' dalam praktiknya di sini di cstheory.SE adalah bahwa pertanyaan biasanya menghasilkan badai 'no true scotsman' di mana setiap jawaban yang tidak disukai OP dianggap "tidak wajar" untuk perangkat yang berevolusi / berubah. alasan.
Suresh Venkat
6
@ Sasho, saya pribadi membaca "alami" tanpa klarifikasi lebih lanjut sebagai maknanya: itu bukan masalah buatan yang dibuat-buat untuk menjawab pertanyaan (atau yang serupa), orang-orang tertarik pada masalah secara mandiri.
Kaveh

Jawaban:

17

Saya pikir jawabannya adalah ya, bahkan hari ini tidak ada masalah alami yang diketahui adalah kandidat untuk melanggar dugaan Isomorfisme.

Alasan utama adalah bahwa biasanya masalah NP-lengkap alami sangat mudah dilihat sebagai paddable, yang menunjukkan Berman dan Hartmanis cukup untuk menjadi isomorfik terhadap SAT. Untuk masalah yang berhubungan dengan grafik alami, ini biasanya melibatkan penambahan simpul tambahan yang, misalnya, terputus dari grafik, atau terhubung dengan cara yang sangat khusus (tetapi biasanya jelas). Untuk versi keputusan masalah optimisasi, biasanya melibatkan penambahan variabel dummy baru tanpa kendala. Dan seterusnya.

Joshua Grochow
sumber
1
Ya, pada sebagian besar masalah grafik, padding mudah. Tapi ini mungkin tidak selalu berlaku. Contoh: apakah benar grafik bebas segitiga dan memiliki jalur Hamilton? Di sini, untuk melestarikan properti, sebuah padding vertex baru harus terhubung ke beberapa yang lama (untuk memungkinkan jalur Hamiltonian), itu harus terhubung ke set independen (untuk menghindari membuat segitiga), dan set independen ini harus sedemikian rupa sehingga mengandung endpoint dari setidaknya satu jalur Hamiltonian (untuk membuatnya bisa diperpanjang ke simpul baru). Tidak terlihat jelas bagi saya bagaimana mencapai ini. Tentu saja, orang mungkin menemukan cara lain untuk pad, saya tidak yakin.
Andras Farago
4
Untuk Hamiltonian Path, lihat makalah Berman-Hartmanis asli (Thm 7 (5) dalam versi STOC, Thm 8 (5) dalam versi jurnal: dx.doi.org/10.1137/0206023 ). Konstruksi mereka tidak memperkenalkan siklus 3-diarahkan baru. Jika Anda ingin menghindari bahkan segitiga tidak terarah, Anda dapat membagi beberapa tepi dalam konstruksi mereka dengan simpul baru. Anda mungkin juga menemukan makalah tindak lanjut mereka menarik, di mana mereka menunjukkan persamaan Diophantine kuadrat adalah p-iso untuk SAT: dx.doi.org/10.1016/0022-0000(78)90027-2
Joshua Grochow
1
@ JoshuaGrochow Apakah ada contoh yang tidak wajar terhadap dugaan BH?
T ....
2
@Turbo: Ya, set k-creative ("set lengkap terenkripsi") dari Joseph dan Young 1985: dx.doi.org/10.1016/0304-3975(85)90140-9
Joshua Grochow