Intermediate

Masalah partisi adalah NP-lengkap lemah karena memiliki algoritma waktu polinomial (semu-polinomial) jika bilangan bulat input dibatasi oleh beberapa polinomial. Namun, 3-Partition adalah masalah NP-lengkap sangat bahkan jika bilangan bulat input dibatasi oleh polinomial.

Dengan asumsi, , dapatkah kita membuktikan bahwa masalah NP-complete antara harus ada? Jika jawabannya ya, apakah ada masalah kandidat yang "alami"?$\mathsf{P \ne NP}$

Di sini, masalah NP-intermediate antara adalah masalah yang tidak memiliki algoritma waktu pseudo-polinomial atau NP-complete dalam arti yang kuat.

Saya kira ada hierarki tak terbatas dari masalah NP-intermediate antara lemah-NP-lengkap dan NP-lengkap.

EDIT 6 Maret : Seperti yang disebutkan dalam komentar, cara alternatif untuk mengajukan pertanyaan adalah:

Dengan asumsi, , dapatkah kita membuktikan adanya masalah NP-complete yang tidak memiliki algoritma waktu polinomial atau NP-complete ketika input numerik disajikan dalam unary? Jika jawabannya ya, apakah ada masalah kandidat yang "alami"?$\mathsf{P \ne NP}$

EDIT2 6 Maret : Arah sebaliknya dari implikasi itu benar. Keberadaan "intermediate" seperti masalah -Lengkap menyiratkan P ≠ N P karena jika P = N P kemudian unary N P masalah -Lengkap berada di P .$NP$$\mathsf{P \ne NP}$$\mathsf{ P=NP}$$NP$$P$

$NP$

$k$$n$$A = \{a_1,...,a_n\}$$k$$S_1,...,S_k ⊆ \{a_1,...,a_n\}$$sum(S_1) = ... = sum(S_k)$

$NP$$k= O(1)$$k > 2$$NP$$k= \Omega(n)$

$k= \omega(1)$$k= O(\log n)$$k$$NP$$NP$

Referensi:

CIELIEBAK, EIDENBENZ, PAGOURTZIS, dan SCHLUDE, TENTANG KOMPLEKSITAS VARIASI SUMBER SUMBER SUMBER, Nordic Journal of Computing 14 (2008), 151–172