Dengan asumsi bahwa P! = NP, saya percaya telah ditunjukkan bahwa ada masalah yang tidak ada dalam P dan bukan NP-Lengkap. Grafik Isomorfisme diduga sebagai masalah seperti itu.
Apakah ada bukti lebih banyak 'lapisan' dalam NP? yaitu hirarki lebih dari tiga kelas mulai dari P dan memuncak dalam NP, sehingga masing-masing adalah superset yang tepat dari yang lain?
Apakah mungkin hierarki itu tidak terbatas?
cc.complexity-theory
Aryabhata
sumber
sumber
Jawaban:
Iya nih! Faktanya, terbukti ada hirarki tak terbatas dari masalah yang semakin sulit antara P dan NP-lengkap dengan asumsi bahwa P! = NP. Ini adalah akibat langsung dari bukti dari Teorema Ladner (yang membentuk non-kekosongan NP \ P)
Secara formal, kita tahu bahwa untuk setiap himpunan S tidak dalam P, ada S 'tidak dalam P sehingga S' adalah karp-dapat direduksi menjadi S tetapi S tidak Cook-dapat direduksi menjadi S '. Oleh karena itu, jika P! = NP, maka ada urutan tak berhingga dari set S 1 , S 2 ... di NP \ P sehingga S i + 1 adalah Karp-dapat direduksi menjadi S i tetapi S i tidak dapat direduksi menjadi S i + 1 .
Memang, sebagian besar masalah seperti itu pada dasarnya sangat tidak wajar.
sumber
Ada gagasan "nondeterminisme terbatas" yang membatasi bit non-deterministik yang diperlukan oleh mesin Turing untuk sampai pada solusi. NP kelas membutuhkan misalnya O (n) bit. Dengan membatasi bit non-deterministik ke polylog mendefinisikan hierarki kelas kompleksitas tak terbatas yang disebut hirarki beta P semua dengan masalah lengkap mereka sendiri.
Lihat, misalnya, artikel berikut untuk perincian: Goldsmith, Levy, Mundhenk, "Nondeterminisme terbatas", SIGACT News, vol 27 (2), halaman 20-29, 1996.
sumber