Masalah NP-lengkap alami dengan saksi "besar"

Pertanyaan pada cstheory " Apa itu NP terbatas untuk saksi ukuran linier? " Bertanya tentang kelas NP terbatas pada saksi ukuran linear , tetapi$O(n)$

Apakah ada masalah NP-complete alami di mana (ya) contoh ukuran membutuhkan saksi ukuran lebih besar dari ?$n$$n$

Jelas kita dapat membangun masalah buatan seperti:

• $L = \{ 1^nw \mid w \text{ encodes a satisfiable formula and } |w|=n \}$
• $L = \{ \varphi \mid \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$

Setelah melihat sekilas pada G&J, setiap masalah NPC alami tampaknya memiliki saksi (secara ketat) lebih kecil dari .$n$

Apakah ada "alasan / penjelasan" untuk itu?

Bagaimana dengan angka pewarnaan tepi dalam grafik padat (alias indeks kromatik )? Anda diberi matriks adjacency dari grafik vertex ( input bit), tetapi saksi alami yang menggambarkan pewarnaan memiliki ukuran . Tentu saja, mungkin ada bukti yang lebih pendek untuk grafik kelas 1 dalam teorema Vizing .$n$$n^2$$n^2\log n$

Lihat juga pertanyaan yang mungkin terkait ini

Saya datang bersama beberapa masalah NP-lengkap yang cukup alami yang tampaknya membutuhkan saksi panjang. Masalahnya, yang diparameterisasi oleh integer dan adalah sebagai berikut:$C$$D$

Input: Satu-rekaman TM Pertanyaan: Apakah ada beberapa , sehingga membuat lebih dari langkah pada beberapa input panjang ?$M$
$n\in\mathbb{N}$$M$$Cn+D$$n$

Kadang-kadang komplemen dari masalah lebih mudah untuk dinyatakan: Apakah satu-tape TM berjalan dalam waktu , yaitu. apakah itu membuat langkah paling banyak pada semua input ukuran , untuk semua ?$M$$Cn+D$$Cn+D$$n$$n$

Hasil lengkapnya disajikan di sini . Pada dasarnya, ditunjukkan bahwa jika kita ingin memverifikasi apakah TM satu-pita berjalan dalam waktu , kita hanya perlu memverifikasi ini pada input panjang yang dibatasi oleh , di mana adalah angka keadaan input TM. Jadi saksi akan menjadi input dengan panjang yang batas waktunya dilanggar. Juga ditunjukkan dalam referensi bahwa masalah-masalah ini adalah NP-lengkap untuk semua dan .$Cn+D$$q^{O(C)}$$q$$q^{O(C)}$$C\geq 2$$D\geq 1$

Sekarang jika saksi adalah input yang melanggar waktu berjalan, itu harus panjang secara umum. Dan inputnya panjang .$q^{\Omega(C)}$$O(q^2)$

Berikut ini adalah contoh, yang muncul masalah alami.

Instance: bilangan bulat positif, d 1 , … , d n dan k , semua dibatasi dari atas oleh n .$d_1,\ldots,d_n$$k$$n$

Pertanyaan: Apakah ada grafik k -colorable dengan deret derajat d 1 , … , d n ?$k$$d_1,\ldots,d_n$

Di sini input dapat dideskripsikan dengan O ( n log n ) bit, tetapi saksi mungkin memerlukan Ω ( n 2 ) bit.$O(n\log n)$$\Omega(n^2)$

Catatan: Saya tidak memiliki referensi bahwa masalah khusus ini memang NP-lengkap. Tetapi persyaratan k- colorability dapat diganti dengan kondisi NP-complete lainnya; masalahnya mungkin akan menjadi NP-lengkap untuk beberapa kondisi, jika tidak untuk yang satu ini.$k$

Mungkin ini adalah "alasan / penjelasan" konyol, tetapi untuk banyak masalah NP-Complete, solusi adalah subset dari input (knapsack, vertex cover, klik, mendominasi set, set independen, max cut, jumlah subset, ... ) atau permutasi atau penugasan ke subset dari input (jalur Hamilton, salesman keliling, SAT, grafik isomorfisma, pewarnaan grafik, ...).

Kita bisa mencoba membaca lebih dalam dari itu, atau mengemukakan alasan yang lebih jelas, tetapi saya tidak yakin apakah ada sesuatu yang lebih dalam atau tidak.

Adapun pertanyaan pertama Anda, Allender menyatakan (dalam Amplifying Lower Bounds oleh Cara Reducibilitas Diri ) bahwa tidak ada masalah NP-lengkap alami yang diketahui berada di luar NTIME (n). Ini berarti bahwa semua set NP-lengkap alami yang diketahui memiliki saksi ukuran linier.

Pertimbangkan varian masalah MAXCLIQUE berikut .

Instance: Sirkuit C dengan bit input 2 n , dan ukuran terikat secara polinomi dalam n . Sirkuit ini secara implisit menentukan grafik pada simpul 2 n , sehingga setiap simpul diidentifikasi dengan string n- bit, dan dua simpul dihubungkan dengan tepi jika string 2 n- bit yang diperoleh dengan menggabungkan dua ID simpul, adalah diterima oleh C . Misalkan G ( C ) menunjukkan grafik ini. Catatan bahwa ia memiliki eksponensial banyak simpul di n , namun masih ditentukan oleh deskripsi ukuran polinomial C .$C$$2n$$n$$2^n$$n$$2n$$C$$G(C)$$n$$C$

Pertanyaan: Apakah G ( C ) mengandung kelompok ukuran n k , di mana k adalah konstanta tetap?$G(C)$$n^k$$k$

Catatan:

1. Masalahnya adalah NP-complete. Penahanan di N P jelas. Kelengkapan dapat dibuktikan dengan mengamati bahwa jika rangkaian hanya menerima titik pasang di mana setiap ID paling banyak N = 2 n k , maka G ( C ) dapat menjadi sewenang-wenang N grafik -vertex plus banyak simpul terisolasi. ( Grafik N -vertex semacam itu dapat dikodekan dalam C , karena C diizinkan untuk memiliki ukuran polinomial dalam n , dan begitu juga dalam N. ) Kemudian pertanyaannya menjadi: apakah ada klik ukuran N / 2 pada $NP$$N=2n^k$$G(C)$$N$$N$$C$$C$$n$$N$$N/2$$N$grafik -vertex? Ini dikenal sebagai NP-lengkap, untuk N umum . Masalah yang N tidak sembarangan, itu dibatasi untuk N = 2 n k , dapat dihilangkan dengan bantalan yang tepat.$N$$N$$N=2n^k$

2. Saksi alami untuk masalah asli adalah n k -sized clique, yang dapat digambarkan oleh O ( n k + 1 ) string panjang (sebuah n tali-bit untuk masing-masing n k simpul). Perhatikan bahwa k dapat berupa konstanta yang sangat besar, sehingga saksi bisa lebih lama dari linear. (Bahkan jika ukuran input adalah deskripsi C , daripada n , saksi ini masih bisa lebih lama, karena k dapat dipilih secara independen dari C. )$n^k$$O(n^{k+1})$$n$$n^k$$k$$C$$n$$k$$C$

3. Masalahnya dapat dilihat sebagai hal yang wajar, karena ini adalah varian dari MAXCLIQUE .

4. Ketika Allender menulis "tidak ada masalah NP-lengkap alami yang diketahui berada di luar N T I M E ( n ) ," (lihat Memperkuat Batas Bawah dengan Cara Reducibilitas Diri , Bagian 7), ia mungkin memiliki konsep yang lebih sempit tentang kealamian dalam pikiran. Sebagai contoh, alami dapat dipersempit menjadi sesuatu yang orang benar - benar ingin pecahkan dengan alasan motivasi yang mandiri dan praktis. Tidak cukup jika masalahnya tidak dibangun melalui diagonalisasi.$NTIME(n)$