Apakah "X kedua adalah NP-lengkap" menyiratkan "X adalah NP-lengkap"?

Masalah " kedua " adalah masalah menentukan keberadaan solusi lain yang berbeda dari beberapa solusi yang diberikan misalnya masalah. $X$

Untuk beberapa masalah -complete, versi solusi kedua adalah -complete (memutuskan keberadaan solusi lain untuk masalah penyelesaian persegi Latin parsial) sementara untuk yang lain itu adalah sepele (SAT SATU NAE) atau tidak bisa -complete (siklus Hamiltonian kedua dalam grafik kubik) di bawah dugaan kompleksitas yang diyakini secara luas. Saya tertarik pada arah yang berlawanan. $NP$ $NP$ $NP$

Kami mengasumsikan alami masalah di mana ada alami verifier efisien yang memverifikasi alami menarik hubungan di mana adalah sebuah contoh input dan adalah saksi singkat keanggotaan dari di . Semua saksi tidak bisa dibedakan dengan pemverifikasi. Keabsahan saksi harus diputuskan dengan menjalankan verifikasi alami dan tidak memiliki pengetahuan tentang saksi yang benar (kedua contoh dalam komentar adalah solusi menurut definisi). $NP$ $X$ $(x, c)$ $x$ $c$ $x$ $X$

Apakah " kedua adalah NP-lengkap" menyiratkan " adalah NP-lengkap" untuk semua masalah "alami" ? $X$ $X$ $X$

Dengan kata lain, Apakah ada masalah "alami" mana implikasi ini gagal? $X$ . Atau yang setara,

Apakah ada "alami" masalah di dan tidak diketahui -Lengkap tapi Kedua masalah adalah -Lengkap? $X$ $NP$ $NP$ $X$ $NP$

$X$ $NP$ $X$

$X$

$NP$ $NP$ $NP$

cc.complexity-theory unique-solution Mohammad Al-Turkistany
sumber

Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .

Bjørn Kjos-Hanssen

EDIT 3 dan EDIT 1 Anda tampaknya tidak sejajar. Jika Anda ingin ini menjadi hasil umum, berguna untuk menyederhanakan bukti kelengkapan NP, Anda juga tidak bisa mengatakan Anda hanya ingin contoh tandingan "tidak dibuat-buat". Juga, akan berguna untuk memiliki definisi "alami / menarik", yang tidak didasarkan pada pendapat pribadi.

Chris Jefferson

Jawaban:

Tidak,

Pertimbangkan masalah "Temukan subset dari himpunan bilangan bulat S yang berjumlah 0".

Masalah ini sepele, karena seseorang dapat mengembalikan set kosong.

Namun, menemukan solusi kedua setelah mengembalikan set kosong adalah masalah jumlah subset yang terkenal, yang dikenal sebagai NP-complete.

Chris Jefferson
sumber

Kecuali Anda dapat mendefinisikan masalah "tidak wajar", ini tidak masalah. Orang mendefinisikan ratusan varian masalah seperti jumlah bagian dan SAT.

Chris Jefferson

@Mohammad: Ini contoh lain; Saya serahkan kepada Anda untuk memutuskan apakah itu alami atau tidak: Sebuah permainan bimatrix selalu memiliki setidaknya satu ekuilibrium Nash dan sulit untuk memutuskan apakah sebuah permainan bimatrix memiliki lebih dari satu ekuilibrium Nash [Gilboa dan Zemel, GEB 1989] . Konstruksi mengambil rumus SAT f dan menghasilkan permainan dengan ekuilibrium Nash tertentu dari bentuk yang diketahui yang selalu ada, sehingga permainan memiliki keseimbangan kedua jika rumus f memuaskan.

Rahul Savani

f : {0, 1, 2, \dots, 2^{n} - 1} \to {0, 1}

$f : \{0,1,2,\ldots,2^n-1\} \to \{0,1\}$

f (0) = 0

$f(0) = 0$

f (2^{n} - 1) = 1

$f(2^n-1)=1$

k

$k$

f (k) = 0

$f(k) = 0$

f (k + 1) = 1

$f(k+1) = 1$

NP selesai tidak berarti bahwa semua instance sulit, hanya beberapa saja. Ada banyak contoh sepele dari jumlah subset (semua masalah yang mengandung 1 dan - 1 misalnya) dan banyak masalah SAT mudah (2 SAT misalnya), tetapi SAT secara keseluruhan masih lengkap dengan NP.

Chris Jefferson

Jawabannya harus merupakan himpunan bagian dari himpunan bilangan bulat S. {} adalah himpunan bagian S karena himpunan kosong adalah himpunan bagian dari semua himpunan. {ϕ} bukan bagian dari S, karena S tidak mengandung ϕ

Chris Jefferson

$ASP$ $NP$

$NP$

Mohammad Al-Turkistany
sumber

Masalah Anda adalah apakah kelengkapan NP dari solusi kedua menyiratkan kelengkapan NP. Apa yang mereka perlihatkan lebih lemah, mereka membutuhkan kelengkapan ASP, karena kelengkapan NP tidak cukup, seperti yang ditunjukkan dalam komentar untuk pertanyaan Anda.

domotorp

Jika ada yang membaca ini, jawaban ini salah. Mudah untuk menghasilkan masalah di mana X kedua adalah NP-lengkap, tetapi X tidak NP-lengkap. Sebagai contoh (seperti yang dibahas dalam komentar di atas), masalah menemukan subset dari himpunan bilangan bulat yang berjumlah 0 adalah NP-X Kedua, karena NP-selesai begitu kita menolak solusi mudah pertama dari set kosong .

Chris Jefferson

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Sasho Nikolov

Agak aneh bagi seseorang untuk mengajukan pertanyaan, menjawabnya dan menerimanya saat diskusi sedang berlangsung.

Chandra Chekuri

@ MohammadAl-Turkistany Komentar saya mengatakan bahwa jawaban Anda tampaknya telah mendapatkan logika mundur, dan tidak menjawab pertanyaan Anda sendiri. Saya tidak mengatakan apa-apa tentang contoh Chris (yang bagi saya terlihat baik-baik saja, tetapi saya tidak ingin membahas argumen itu di komentar).

Sasho Nikolov