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.
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.
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?
sumber
Jawaban:
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.
sumber