Bisakah masalah yang terbatas ada pada NP-Complete?

Dosen saya membuat pernyataan

Masalah yang terbatas tidak dapat NP-Lengkap

Dia berbicara tentang Sudoku pada saat itu mengatakan sesuatu di sepanjang garis bahwa untuk 8x8 Sudoku ada satu set solusi yang terbatas tetapi saya tidak ingat persis apa yang dia katakan. Saya menulis catatan yang saya kutip tetapi masih tidak begitu mengerti.

Sudoku NP lengkap jika aku tidak salah. Masalah klik juga NP-Lengkap dan jika saya punya masalah 4-klik apakah ini bukan masalah yang terbatas yaitu NP-Lengkap?

np-complete np TheRapture87
sumber

Apa itu 'masalah terbatas'? Google dan Wikipedia tidak membantu.

Anton Trunov

@AntonTrunov Masalah di mana input memiliki panjang terikat.

Yuval Filmus

@YuvalFilmus, Bukankah itu benar dari semua pasangan input mesin Turing * yang valid? IIRC salah satu simbol ditetapkan sebagai simbol kosong dan input awalnya memiliki wilayah terbatas di luar yang simbol selain simbol kosong tidak dapat muncul. Istilah "NP complete" biasanya tidak digunakan dalam konteks operasi pada stream yang tidak dapat dimodelkan tanpa melonggarkan asumsi itu.

Mike Samuel

@MikeSamuel Ketika saya mengatakan panjang terikat, maksud saya input ukuran paling banyak 100. (Atau nomor apa pun selain 100.)

Yuval Filmus

@YuvalFilmus, ok. Saya katakan, istilah "NP complete" hanya digunakan ketika tidak ada simbol non-kosong pada input atau ada bilangan bulat yang merupakan jumlah simbol antara simbol non-kosong paling kiri dan simbol non-kosong paling kanan . 100 akan menjadi contoh seperti itu.

Mike Samuel

Jawaban:

Jika masalah hingga adalah NP-lengkap maka P = NP, karena setiap masalah hingga memiliki algoritma waktu polinomial (bahkan algoritma waktu konstan).

Ketika kami mengatakan bahwa Sudoku adalah NP-lengkap, kami berarti bahwa versi umum dari Sudoku yang dimainkan pada papan adalah NP-complete. $n^2 \times n^2$

Akhirnya, masalah 4-klik, meskipun bukan masalah yang terbatas (grafik input memiliki ukuran tidak terbatas), adalah masalah mudah yang memiliki algoritma waktu polinomial.

Yuval Filmus
sumber

Jadi, apakah masalah 4-klik P karena memiliki algoritma waktu polinomial?

TheRapture87

@ Aceboy1993 Benar, itulah definisi P.

Yuval Filmus

Tapi mengapa K-klik dianggap sebagai NP-Lengkap? Apakah K tidak hanya mewakili angka seperti 4?

TheRapture87

k

$k$

k

$k$

Juga, kita dapat membuktikan bahwa Clique adalah NP-complete.

Yuval Filmus

Pernyataan guru Anda salah atau mungkin Anda tidak mendengarnya dengan benar. Pernyataan yang benar adalah

$L$ $|L| \geq 1$ $P = NP$

$P \neq NP$ $|L|>1$ $\emptyset$ $P=NP$ atau $P \neq NP$ .

Sudoku atau catur tidak lengkap NP (seperti yang ditunjukkan Yuval), karena input mereka berukuran papan 9x9 atau 8x8 yang terbatas (saya berbicara tentang versi keputusan, apakah sudoku memiliki solusi atau apakah catur memiliki strategi menang). Dalam catur, saya mengasumsikan jika Anda mengulangi posisi, itu dianggap seri.

Shreesh
sumber

Ingat: Masalah X adalah NP-complete iff memenuhi dua kriteria:

a) Ada dalam NP - Yaitu solusi dugaan X dapat diverifikasi dalam waktu polinomial.

b) Lengkap untuk NP - Yaitu Setiap masalah Y di NP memiliki pengurangan waktu polinomial yang menerjemahkan sebuah instance Y ke instance X (sehingga setiap program waktu polinomial yang memecahkan X juga akan menyelesaikan Y dalam waktu polinomial) ).

Kami dapat menyetujui bahwa Sudoku 9x9 memuaskan (a). Ini adalah (b) di mana segala sesuatu jatuh. Lebih umum - Masalah (dalam NP atau sebaliknya) biasanya memiliki contoh ukuran N untuk nilai N besar yang semena-mena ; tentu ini berlaku untuk masalah yang dikenal di NP. Pengurangan dari masalah seperti itu menjadi masalah yang memiliki ukuran masalah maksimum yang mungkin tidak mungkin merupakan pengurangan instance-to-instance yang valid, karena yang pertama selalu memiliki (jauh) lebih banyak instance daripada yang terakhir. Itu sebabnya Sudoku harus digeneralisasi ke matriks NxN sebelum orang dapat mempertimbangkan kelengkapan NP.

PMar
sumber

Ini tidak benar. Sangat mungkin untuk memiliki reduksi yang valid dari masalah dengan banyak instance tak terhingga ke masalah dengan banyak instance tak terbatas. Sebagai contoh, berikut adalah reduksi dari SAT ke masalah penentuan apakah string panjang-1 sama dengan "a": jika instance SAT memuaskan, petakan ke string "a"; jika tidak, petakan ke string "b". Sekarang, pengurangan itu (mungkin) tidak dapat dihitung dalam waktu polinomial tetapi pengurangan yang benar-benar valid.

David Richerby