Kandidat alami untuk hierarki di dalam NPI

Mari kita asumsikan bahwa . adalah kelas masalah di yang tidak ada di atau di -hard. Anda dapat menemukan daftar masalah yang diduga sebagai sini . $\mathsf{P} \neq \mathsf{NP}$ $\mathsf{NPI}$ $\mathsf{NP}$ $\mathsf{P}$ $\mathsf{NP}$ $\mathsf{NPI}$

Teorema Ladner memberi tahu kita bahwa jika maka ada hierarki tak terbatas dari masalah , yaitu ada masalah yang lebih sulit daripada yang lain masalah. $\mathsf{NP}\neq\mathsf{P}$ $\mathsf{NPI}$ $\mathsf{NPI}$ $\mathsf{NPI}$

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 \in \mathsf{NP}$
$A$ $B$ $\mathsf{NPI}$
$A$ $B$
$B$ $A$

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. $B$ $A$

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? $\mathsf{NPI}$ $\mathsf{NP}$

complexity-theory np-hard Mohammad Al-Turkistany
sumber

Jadi, Anda mencari masalah sedemikian rupa sehingga dengan dan ?

P \in N P

$P \in \mathrm{NP}$

P_{1} \leq_{p} P \leq_{p} P_{2}

$P_1 \leq_p P \leq_p P_2$

P_{1} \in N P I

$P_1 \in \mathrm{NPI}$

P_{2} \in N P C

$P_2 \in \mathrm{NPC}$

Raphael

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

ada beberapa masalah dengan status yang mirip dengan anjak piutang, lihat makalah ini oleh teori

Marcos Villagra

selain itu, kami memiliki daftar yang sangat bagus di cstheory cstheory.stackexchange.com/questions/79/…

Marcos Villagra

mengapa daftar yang Marcos tautkan bukan jawaban untuk pertanyaan Anda?

Suresh

Jawaban:

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. $n$ $x$ $y$ $x! \mod y$

Marcos Villagra
sumber

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

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?

n

$n$

k

$k$

n

$n$

d

$d$

1 < d \leq k

$1 < d \le k$

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.

x! \mod y

$x!\mod y$

k

$k$

Marcos Villagra