Kompleksitas menemukan solusi kedua memberikan solusi yang benar untuk masalah NP-complete

17

Saya mencari tahu apakah ada hasil umum tentang atau contoh tentang kelengkapan NP dari masalah menemukan solusi kedua untuk masalah NP-lengkap. Lebih tepatnya, saya tertarik dengan masalah apa pun dari formulir berikut:

Diberikan solusi untuk contoh dari masalah NP-complete, apakah ada solusi untuk ? $S$ $I$ $S' \neq S$ $I$

Setiap contoh masalah semacam ini, baik NP-lengkap dan tidak, atau pekerjaan umum, atau bahkan apa yang disebut masalah semacam ini (sehingga saya dapat melakukan pencarian sendiri dengan benar) akan dihargai.

Pertanyaan lain membahas masalah ini secara khusus berkaitan dengan SAT.

Saya harap saya tidak menanyakan sesuatu yang sangat mendasar; sepertinya tidak ada contoh di Garey dan Johnson tentang hal semacam ini.

Terima kasih
Mark C.

cc.complexity-theory reference-request np-hardness unique-solution Mark C.
sumber

Tandai, jika cstheory.stackexchange.com/questions/1639/... menjawab pertanyaan Anda, beri tahu saya, dan kami dapat menandainya sebagai duplikat. Saya bertanya karena pertanyaan Anda tampaknya cukup terbuka, dan mungkin jawaban di sana mungkin membantu

Suresh Venkat

Ah, ya, sepertinya menjawabnya. Jelas, "Masalah Solusi Lain" adalah apa yang saya cari. Terima kasih!

Mark C.

1

Jawaban Tsuyoshi tampaknya sangat berbeda dari yang lain, jadi saya tidak yakin masuk akal untuk menutup pertanyaan ini. Mungkin Mark, Anda dapat menambahkan catatan ke pembaca penerusan pertanyaan ke pertanyaan lain (yang khusus untuk SAT)?

Suresh Venkat

15

Pertanyaannya sepertinya sudah terpecahkan ketika saya menulis jawaban ini, tetapi biarkan saya tetap mengirim jawaban saya.

Yato dan Seta [YS03] (keduanya adalah kolega saya ketika saya masih mahasiswa) mengusulkan kerangka umum untuk membuktikan NP-kelengkapan dari masalah semacam ini, di mana mereka disebut Another Solution Problem atau ASPs, dan membuktikan NP-kelengkapan dari ASP dari banyak teka-teki. Mereka menganggap gagasan terbatas pengurangan antara masalah hubungan yang disebut pengurangan ASP, dan menunjukkan bahwa NP-hardness ASP disimpan di bawah pengurangan ASP dan menunjukkan bahwa banyak pengurangan yang diketahui sebenarnya dapat dilihat sebagai atau dimodifikasi untuk pengurangan ASP antara masalah hubungan alami.

[YS03] Takayuki Yato dan Takahiro Seta. Kompleksitas dan kelengkapan menemukan solusi lain dan penerapannya pada teka-teki. Transaksi IEICE tentang Pokok-pokok Elektronika, Komunikasi dan Ilmu Komputer , E86-A (5): 1052-1060, Mei 2003.

Tsuyoshi Ito
sumber

1

Saya kenal seseorang yang mempertimbangkan ini sebagai arah yang mungkin untuk tesis PhD, dan kami membicarakannya secara singkat, meskipun saya tidak tahu apa-apa tentang area tersebut. Sepertinya tidak ada banyak tindak lanjut sejak makalah yang Anda kutip, meskipun mungkin keterampilan pencarian saya lemah. Apakah Anda mengetahui adanya makalah penting sejak tahun 2003?

Aaron Sterling

3

@ Harun: Ada masalah lain yang ditunjukkan FNP-lengkap di bawah ASP reducibility. Juga, ada beberapa makalah tentang hal ini oleh Takayuki dan yang lainnya (termasuk satu makalah di mana saya adalah rekan penulis :)), dan Takayuki menulis tesis PhD tentang topik ini. Salah satu perbaikan selanjutnya adalah formulasi berdasarkan masalah janji, yang menjadi penting terutama ketika kita berurusan dengan PSPACE-kelengkapan dan EXP-kelengkapan ASP. Sayangnya, tidak ada satu pun kertas yang tampaknya tersedia secara bebas (saya merasa bodoh, tetapi bahkan saya tidak dapat mengakses kertas saya sendiri di balik paywall). Anda mungkin ingin menghubunginya.

Tsuyoshi Ito

2

+1 untuk jawaban yang bagus, dan untuk "bahkan saya tidak dapat mengakses kertas saya sendiri di balik paywall", hehe

Daniel Apon

7

Diberi sirkuit Hamilton dalam grafik, cari sirkuit hamilton lain. Ini lengkap dengan FNP. Menariknya, ada masalah di mana "solusi lain" dijamin ada dengan argumen paritas. Misalnya: Diberi sirkuit Hamilton dalam grafik 3-reguler, cari sirkuit Hamilton kedua. Perhatikan bahwa menemukan sirkuit hamiltonian dalam grafik 3-reguler adalah NP-complete. Menemukan yang kedua, mengingat grafiknya adalah hamiltonian, ada di PPA.

Lihat posting blog saya untuk lebih jelasnya.

Siwa Kintali
sumber

NAE-SAT juga. selalu memiliki sejumlah solusi.

Suresh Venkat

Menurut dikotomi di atas, NAE-SAT yang lain dapat dipecahkan secara polinomi (sebagaimana dinyatakan dalam makalah ini).

Mohammad Al-Turkistany

Tentu. tapi itu jauh lebih mudah untuk NAE-SAT: ambil tugas yang diberikan dan balikkan. waktu linier! :)

Suresh Venkat

7

Laurent Juban dalam Teorema Dikotomi untuk Masalah Kesederhanaan Unik yang Generalized membuktikan teorema dikotomi untuk SAT lain yang didefinisikan sebagai:

$\phi$ $m$ $\phi$

$\phi$ $m$

Berikut kutipan dari makalah dengan teorema dikotomi:

$S$ $S$ $NP$ $coNP$

$S$

$S$

$S$

$S$

$S$

$S$

Mohammad Al-Turkistany
sumber

S = {⊥, x \lor y \lor \neg z, x \lor \neg y \lor \neg z}

$S=\{\bot,x\lor y\lor\neg z,x\lor\neg y\lor\neg z\}$

S

$S$

S

$S$

S

$S$

⊥

$\bot$

S^{'}

$S'$

S^{'} = S ∖ {⊥}

$S'=S\setminus\{\bot\}$ mematuhi kondisi 1, maka itu setidaknya dua secara eksplisit memberikan tugas yang memuaskan.

Emil Jeřábek mendukung Monica

S

$S$

1

Berikut adalah contoh lain dari makalah ini KOMPLEKSITAS KOMPUTASI MENGAKUI SET KRITIS :

$NP$

$G$

Pertanyaan : Apakah ada sisi-partisi lain yang berbeda dari yang diberikan?

$NP$

$P$ $P$

Pertanyaan : Apakah ada penyelesaian lain untuk kotak Latin?

Mohammad Al-Turkistany
sumber

Kompleksitas menemukan solusi kedua memberikan solusi yang benar untuk masalah NP-complete

Jawaban: