Bagaimana cara membuktikan suatu masalah BUKAN NP-Lengkap?

17

Apakah ada teknik umum untuk membuktikan masalah BUKAN NP-Lengkap?

Saya mendapat pertanyaan ini pada ujian yang meminta saya untuk menunjukkan apakah beberapa masalah (lihat di bawah) adalah NP-Complete. Saya tidak bisa memikirkan solusi yang nyata, dan hanya membuktikannya dalam P. Jelas ini bukan jawaban yang nyata.

NP-Complete didefinisikan sebagai sekumpulan masalah yang ada dalam NP, dan semua masalah NP dapat dikurangi. Jadi bukti apa pun harus bertentangan dengan setidaknya satu dari dua kondisi ini. Masalah khusus ini, memang dalam P (dan dengan demikian dalam NP). Jadi saya tidak dapat membuktikan bahwa ada beberapa masalah dalam NP yang tidak dapat direduksi menjadi masalah ini. Bagaimana bisa ini dibuktikan ??

Berikut adalah masalah khusus yang saya alami pada ujian:

Biarkan DNF menjadi himpunan string dalam bentuk normal disjungtif . Misalkan DNFSSEBUAHT menjadi bahasa string dari DNF yang memuaskan oleh beberapa penugasan variabel. Tunjukkan apakah DNFSSEBUAHT ada dalam NP-Complete.

Tanpa judul
sumber
8
Jika DNF-SAT dapat dibuktikan tidak menjadi NP-lengkap, itu akan segera menyiratkan bahwa , seperti yang telah Anda tunjukkan. Jadi, saya percaya jawaban yang mereka cari adalah apa yang Anda berikan (dan Anda mungkin seharusnya secara implisit berasumsi bahwa P N P ). Namun, ini adalah pertanyaan yang sangat menyesatkan. PNPPNP
Shaull
Anda benar, jadi saya mengerti bahwa masalah ini setara dengan masalah dan solusi untuk satu, juga memecahkan yang lain. P=NP
Tanpa Judul
Mengapa Anda mengatakan membuktikan bahwa DNFSAT ada di P bahwa "jelas ini bukan jawaban yang nyata"?
András Salamon
5
@ AndrásSalamon Diasumsikan bahwa , yang merupakan pernyataan yang tidak terbukti. PNP
Tanpa judul
1
@Tidak berjudul: sebenarnya tidak menganggap P ≠ NP, lihat jawaban saya.
András Salamon

Jawaban:

8

Berdasarkan komentar, Anda sepertinya menginginkan jawaban tanpa syarat.

Namun, DNF-SAT berada di L, dengan menugaskan variabel untuk memenuhi disjunct pertama. Karenanya jika NP-complete, maka L = NP.

Di sisi lain, jika L = NP maka DNF-SAT adalah NP-lengkap di bawah pengurangan logspace, sepele. (Bahkan, jika L = NP maka setiap masalah di NP adalah NP-lengkap di bawah pengurangan logspace.)

Oleh karena itu L = NP jika DNF-SAT adalah NP-lengkap di bawah pengurangan ruang log.

Jadi saat ini Anda tidak dapat membuat pernyataan tanpa syarat bahwa DNF-SAT bukan NP-lengkap, seperti yang tampaknya ingin Anda lakukan. Tidak perlu mengasumsikan P ≠ NP, tetapi jawabannya memang harus bergantung pada sesuatu, dan L ≠ NP adalah hipotesis terlemah yang mungkin menjamin hasil yang diinginkan.

András Salamon
sumber
Menarik. Jadi masalah ini setara dengan masalah . Bisakah Anda menjelaskan mengapa Anda mengatakan L N P adalah asumsi yang lemah? L=NP=P=NPCLNP
Tanpa Judul
3
Jika maka ψ lebih lemah dari ϕ . ϕψψϕ
András Salamon
14

Masalah adalah NP-lengkap jika itu adalah baik NP- keras dan di NP. Ini berarti bahwa Anda perlu menyangkal salah satu dari keduanya.Q

  1. Dengan asumsi bahwa P NP, Anda dapat memberikan waktu polinomial pemecahan algoritma Q . Lebih jarang, dengan asumsi bahwa grafik isomorfisma bukan NP-keras, Anda dapat menunjukkan bahwa Q adalah polytime yang dapat direduksi menjadi grafik isomorfisme.QQ
  2. Anda menunjukkan bahwa tidak dalam NP. Ini lebih sulit, dan Anda biasanya harus menggunakan asumsi lain, seperti non-collapse dari hierarki polinomial, bahwa NP coNP atau menunjukkan bahwa sulit untuk beberapa kelas lain lebih tinggi dari NP, misalnya dengan menunjukkan bahwa itu NEXPTIME-hard.Q

Biasanya, jawabannya adalah untuk memberikan algoritma waktu polinomial, yang akan menjadi yang paling sederhana untuk DNF-SAT, tetapi ini bergantung pada hipotesis bahwa P NP. Namun, membuktikan bahwa DNF-SAT bukan NP-lengkap tanpa asumsi, seperti yang ditunjukkan oleh Shaull, membuktikan bahwa P NP, sehingga agak sulit.

Pål GD
sumber
1
Kedua teknik yang Anda berikan terletak pada semacam asumsi yang tidak terbukti. Apakah menurutnya mungkin ada cara konkret (tanpa asumsi) untuk menyelesaikan masalah semacam ini?
Tanpa Judul
Oh, dan saya tidak bermaksud masalah khusus ini, karena seperti yang dikatakan Shaull, masalah ini masih terbuka. Maksud saya membuktikan CoNP-Completeness secara umum.
Tanpa Judul
2
@ Tidak Berjudul Anda mungkin tidak bermaksud melengkapi TNP. Salah satu cara untuk menunjukkannya adalah menurut saya (2), membuktikan bahwa masalahnya adalah NEXPTIME-hard. Kita tahu bahwa NP NEXPTIME, jadi itu akan membuktikannya. Membuktikan bahwa masalah Q adalah NEXPTIME-hard, karena itu berarti bahwa Q tidak bisa di NP dan dengan demikian tidak bisa NP-lengkap. QQ
Pål GD
10

Dengan hierarki waktu nondeterministic, Anda dapat menunjukkan bahwa masalahnya adalah -hard; sebagai N PN E X P , adalah mustahil untuk mengurangi masalah dalam waktu polinomial untuk masalah di N P , sehingga masalah tidak akan di N P .NEXPNPNEXPNPNP

Namun, jika masalah Anda tidak terlalu sulit, Anda mungkin kesulitan untuk membuktikan bahwa itu tidak ada dalam ; dan jika itu adalah di N P , Anda akan sulit ditekan untuk menunjukkan bahwa N P tidak Karp-direduksi menjadi masalah Anda tanpa mengasumsikan bahwa PN P .NP NPNPPNP

Niel de Beaudrap
sumber
0

Seperti halnya dengan semua bukti, tidak ada rumus untuk membuktikan pernyataan, Anda harus melakukan beberapa tebakan cerdas, coba-coba dan semoga Anda akan dapat membuktikan apa yang Anda coba buktikan. Untuk membuktikan suatu masalah BUKAN NP-Lengkap, negasikan definisi (Hukum DeMorgran), artinya buktikan masalah BUKAN dalam NP atau buktikan masalah BUKAN NP-Keras.

saadtaame
sumber
0

Saya percaya apa yang dosen inginkan adalah Anda dapat membedakan masalah yang ada di P dari masalah yang NP-lengkap dalam arti bahasa yang diberikan dapatkah Anda membangun algoritma yang efisien? jika ya maka diduga tidak lengkap NP karena kami tidak berpikir bahasa dalam P lengkap NP! jika tidak, Anda masih harus membuktikan bahwa masalahnya adalah NP-hard!

perhatikan bahwa ada beberapa masalah yang kita tidak tahu statusnya di sana seperti grafik isomorfisme, angka yang diberikan, ... kita berpikir bahwa masalah ini bukan NP-lengkap tetapi tidak ada yang bisa membuktikan itu! secara khusus kami memiliki bukti bahwa isomorfisma grafik tidak lengkap NP! masalah lainnya adalah konjungtur game unik yang kami curigai bahwa game unik itu NP-complete tetapi tidak ada bukti! jadi pendekatan yang Anda jelaskan tidak membantu!

fayez abd-alrzaq deab
sumber