Kandidat alami untuk hierarki di dalam NPI

22

Mari kita asumsikan bahwa . adalah kelas masalah di yang tidak ada di atau di -hard. Anda dapat menemukan daftar masalah yang diduga sebagai sini .N P I N P P N P N P IPNPNPINPPNPNPI

Teorema Ladner memberi tahu kita bahwa jika maka ada hierarki tak terbatas dari masalah , yaitu ada masalah yang lebih sulit daripada yang lain masalah.N P I N P I N P INPPNPINPINPI

Saya mencari kandidat untuk masalah seperti itu, yaitu saya tertarik pada pasangan masalah
- , - dan sebagai , - diketahui mengurangi hingga , - tetapi tidak ada pengurangan diketahui dari ke . A B N P I A B B AA,BNP
ABNPI
AB
BA

Bahkan lebih baik jika ada argumen untuk mendukung ini, misalnya ada hasil yang tidak mengurangi menjadi dengan asumsi beberapa dugaan dalam teori kompleksitas atau kriptografi.ABA

Adakah contoh alami dari masalah seperti itu?

Contoh: Graph Isomorphism problem dan Integer Factorization problem diperkirakan berada di dan ada argumen yang mendukung dugaan ini. Apakah ada masalah keputusan yang lebih sulit daripada keduanya tetapi tidak diketahui sebagai -hard?N PNPINP

Mohammad Al-Turkistany
sumber
1
Jadi, Anda mencari masalah sedemikian rupa sehingga dengan dan ? P 1 p P p P 2 P 1N P I P 2N P CPNPP1pPpP2P1NPIP2NPC
Raphael
1
Ya tapi tidak ada pengurangan yang diketahui dari P ke P1 (sama halnya tidak ada pengurangan yang diketahui dari P2 ke P).
Mohammad Al-Turkistany
2
ada beberapa masalah dengan status yang mirip dengan anjak piutang, lihat makalah ini oleh teori
Marcos Villagra
8
selain itu, kami memiliki daftar yang sangat bagus di cstheory cstheory.stackexchange.com/questions/79/…
Marcos Villagra
2
mengapa daftar yang Marcos tautkan bukan jawaban untuk pertanyaan Anda?
Suresh

Jawaban:

5

Saya telah menemukan masalah yang bagus bernama ModularFactorial . Ambil sebagai input dua digit integer dan , dan output . Masalah ini setidaknya sama sulitnya dengan Anjak dan tidak tahu akan sulit bagi FNP . Referensi adalah buku terbaru (dan indah) karya Cristopher Moore dan Stephan Mertens The Nature of Computation , halaman 79.x ynxyx!mody

Marcos Villagra
sumber
1
Saya percaya OP sedang mencari masalah di NP. Bisakah Anda merumuskan kembali ini sebagai masalah keputusan?
Zach Langley
FNP adalah versi fungsi (yaitu, masalah pencarian) NP. Faktanya, anjak piutang tidak dalam NP, ini adalah FNP. Sebagai contoh, masalah keputusan untuk anjak sepele, kompleksitasnya hanya O (1), tetapi masalah pencarian adalah bagian yang sulit. Karena OP memberi anjak sebagai contoh, saya pikir ini juga merupakan jawaban yang valid.
Marcos Villagra
1
Anjak piutang dapat dirumuskan kembali menjadi masalah keputusan sebagai berikut: diberi bilangan bulat dan bilangan bulat , apakah mengandung faktor dengan ? Apakah ada versi keputusan analog dari masalah ModularFactorial? k n d 1 < d knknd1<dk
Zach Langley
@Marcos, Terima kasih. Saya tertarik dengan masalah keputusan dalam NP.
Mohammad Al-Turkistany
@ZachLangley, ya tentu saja saya setuju, tetapi saya berpikir dalam versi keputusan lain, yaitu, "apakah x memiliki faktor?". Jawabannya ada hanya, "ya" selalu. Anda dapat melakukan hal yang sama dengan modularfactorial, memberikan integer k dan memutuskan apakah lebih besar dari atau tidak. kx!modyk
Marcos Villagra