Adakah masalah NP-complete yang diketahui, baik NP-hard dalam arti kuat atau memiliki algoritma pseudopolinomial?

19

Dalam makalah mereka (hlm. 503) Garey dan Johnson berkomentar:

... mungkin ada masalah NP-complete yang bukan NP-complete dalam arti kuat atau tidak dapat dipecahkan oleh algoritma waktu pseudo-polinomial ...

Adakah yang tahu beberapa masalah kandidat dengan properti yang disebutkan di atas?

Saya pikir jawaban yang mungkin untuk pertanyaan ini dapat berupa daftar masalah NP-lengkap dalam pengertian biasa sehingga tidak ada algoritma pseudopolinomial yang diketahui.

Oleksandr Bondarenko
sumber
5
Bukankah mungkin untuk membuat contoh buatan dengan menggabungkan masalah NP-lengkap dengan algoritma waktu pseudo-polinomial dan bahasa perantara-NP dari teorema Ladner?
Tsuyoshi Ito
2
Jawaban saya yang diposting sebelumnya salah; permintaan maaf saya. Inilah yang terjadi ketika saya melambaikan tangan dan memposting!
Daniel Apon

Jawaban:

17

Saya tidak tahu apakah Anda tertarik mendengar lebih detail dari komentar saya pada pertanyaan Anda, tetapi di sini lebih detail pula.

Jika P = NP, setiap masalah dalam NP dapat diselesaikan dalam waktu polinomial dan oleh karena itu dalam waktu polinomial semu, yang berarti bahwa tidak ada masalah yang memenuhi kebutuhan Anda, seperti yang dicatat Magnus dalam jawabannya. Jadi asumsikan P ≠ NP di sisa jawaban ini.

Karena P ≠ NP, ada bahasa L ∈NP ∖ P yang tidak NP-lengkap (teorema Ladner). Pertimbangkan masalah berikut:

Produk langsung dari partisi dan L
Instance : m bilangan bulat positif a 1 , ..., a m dan k bilangan bulat b 1 , ..., b k ∈ {0,1}.
Pertanyaan : Apakah kedua hal berikut ini berlaku?
(1) m integer a 1 ,…, a membentuk m ya-instance dari masalah Partition.
(2) k -bit string yang b 1 ... b k milik L .

Setelah kertas oleh Garey dan Johnson, tentukan fungsi Panjang sebagai m + ⌈ log maks i a i ⌉ + k dan fungsi Max sebagai maks i a i .

Merupakan rutin untuk memeriksa (i) apakah NP-lengkap dalam arti yang lemah, (ii) tidak memiliki algoritma pseudo-polinomial-waktu, dan (iii) itu bukan NP-lengkap dalam kuat merasakan.

(Petunjuk: (i) Keanggotaan untuk NP mengikuti dari fakta bahwa kedua masalah Partisi dan L berada di NP. Untuk kekerasan NP, kurangi Partisi untuk masalah ini. (Ii) Bangun transformasi pseudo-polinomial dari L ke masalah ini. (iii) Bangun transformasi pseudo-polinomial dari masalah ini ke L dengan menggunakan fakta bahwa Partition memiliki algoritma pseudo-polinomial-waktu.)

Tidak ada yang istimewa tentang masalah Partisi dalam konstruksi ini: Anda dapat menggunakan masalah NP-complete lemah Anda dengan algoritma pseudo-polinomial-waktu.

Tsuyoshi Ito
sumber
Terima kasih atas jawabannya. Saya lebih tertarik pada masalah non-buatan yang bertentangan dengan yang dijelaskan oleh Anda. Meskipun saya ragu tentang definisi masalah non-buatan.
Oleksandr Bondarenko
@Oleksandr: Adapun pilihan L, Anda dapat menggunakan bahasa perantara-NP. Namun, Anda benar bahwa apa pun bahasa L yang Anda pilih, konstruksi ini memberikan masalah buatan karena mengambil produk langsung dengan Partition. Saya tidak tahu masalah alami yang memenuhi kebutuhan Anda.
Tsuyoshi Ito
Lagi pula, jawaban Anda menarik bagi saya dan layak mendapat dukungan.
Oleksandr Bondarenko
(Sunting: Nevermind. :))
Daniel Apon
1

Saya akan mengatakan jawabannya jelas tidak (yaitu, tidak ada yang tahu), karena tidak ada yang tahu apakah masalah NP-complete dapat diselesaikan dalam waktu polinomial , apalagi pseudo -polinomial waktu. (Setiap algoritma polinomial, tentu saja, pseudopolinomial.) Jika Anda dapat menemukan masalah dalam NPC yang tidak dapat diselesaikan dalam waktu pseudopolinomial, Anda baru saja membuktikan bahwa P ≠ NP, jadi saya pikir aman untuk mengatakan bahwa tidak ada contoh seperti itu akan menjadi diproduksi dalam waktu dekat.

Magnus Lie Hetland
sumber
1
Saya telah mengedit pertanyaan saya ke "Apakah ada yang tahu beberapa masalah kandidat ...?"
Oleksandr Bondarenko