Kernel polinomial untuk

Masalah parametrized k-FLIP SAT didefinisikan sebagai:

Input: rumus 3-CNF dengan variabel dan penugasan kebenaran Parameter: Pertanyaan: dapatkah kita mengubah penugasan menjadi penugasan yang memuaskan untuk membalik nilai kebenaran paling banyak variabel ?$\varphi$$n$$\sigma : [n] \to \{0,1\}$
$k$
$\sigma$$\sigma'$$\varphi$ $k$

Masalahnya jelas di FPT ( Stefan Szeider: Kompleksitas Parameterized dari k-flip Local Search untuk SAT dan MAX SAT. Discrete Optimization 8 (1): 139-145 (2011) )

Apakah itu mengakui kernel polinomial? (berdasarkan asumsi kompleksitas yang masuk akal)

Teknik komposisi silang baru-baru ini (lihat Hans L. Bodlaender, Bart MP Jansen, Stefan Kratsch, "Kernelization Lower Bounds By Cross-Composition" ) tampaknya tidak berguna untuk masalah ini. Dan mereka juga tampaknya tidak berguna untuk masalah serupa yang menanyakan apakah solusi tertentu untuk masalah NP-hard dapat ditemukan dari contoh yang diberikan oleh pencarian lokal (membatasi pencarian ke tetangga dari contoh yang diberikan, di bawah beberapa ukuran jarak alami).

Masalahnya tidak memiliki kernel polinomial kecuali NP berada di dalam coNP / poli. Teknik komposisi silang dari makalah kami berlaku dengan cara nontrivial.

Biarkan saya menunjukkan bagaimana masalah Vertex Cover klasik OR-cross-composes ke dalam masalah k-FLIP-SAT; oleh hasil dalam makalah yang dikutip, ini sudah cukup. Konkretnya, kita membangun algoritma polinomial-waktu yang input adalah urutan contoh Vertex Sampul bahwa semua berbagi nilai yang sama dari k dan semua memiliki tepat n simpul. Outputnya adalah turunan dari k -FLIP SAT dengan nilai parameter O ( k $(G_1,k), (G_2, k), \ldots, (G_t, k)$$k$$n$$k$ , yang cukup kecil untuk komposisi silang, sehinggaturunan k -FLIP SAT memiliki jawaban ya jika salah satu grafik input memiliki simpul penutup ukuran k . Dengan menduplikasi satu input (yang tidak mengubah nilai OR) kami dapat memastikan bahwa jumlah input t adalah kekuatan dua.$O(k + \log t)$$k$$k$$t$

Komposisi hasil sebagai berikut. Beri nomor simpul pada grafik setiap input grafik sebagai v i , 1 , v i , 2 , … , v i , n . Buat variabel yang sesuai dalam instance FLIP-SAT untuk setiap simpul dari setiap grafik input. Selain itu, buat variabel pemilih u i untuk setiap nomor instance input i ∈ [ t ] . Untuk setiap grafik input G i , kami menambahkan beberapa klausa ke rumus. Untuk setiap sisi { v i , $G_i$$v_{i,1}, v_{i,2}, \ldots, v_{i,n}$$u_i$$i \in [t]$$G_i$ dari grafik G i , tambahkan klausa ( v i , x ∨ v i , y ∨ ¬ u i ) ke rumus, yang akan menyandikan "salah satu dari titik akhir tepi ini disetel ke true, atau contohnya saya tidak aktif ". Dalam tugas awal, semua variabel vertex diatur ke false dan semua variabel pemilih u $\{v_{i,x}, v_{i,y}\}$$G_i$$(v_{i,x} \vee v_{i,y} \vee \neg u_i)$$i$$u_i$disetel ke false, sehingga semua klausa ini puas. Untuk membangun perilaku-OR ke dalam komposisi, kami akan menambahkan rumus untuk memastikan bahwa tugas yang memuaskan menetapkan setidaknya satu pemilih menjadi true, dan kemudian harus juga membentuk penutup simpul dari grafik yang dipilih.

Untuk memastikan kami dapat melakukan pemilihan ini sambil menjaga jarak flip kecil dibandingkan dengan jumlah input , kami menggunakan struktur pohon biner lengkap dengan daun t , yang memiliki log tinggi t . Jumlah daun dari 1 ke t dan mengasosiasikan saya daun -th dengan variabel u saya bahwa kontrol jika input i aktif atau tidak. Buat variabel baru untuk setiap simpul internal pohon biner. Untuk setiap simpul internal, biarkan variabel yang bersesuaian menjadi x dan variabel dari dua anaknya adalah y dan z . Tambahkan klausa $t$$t$$\log t$$1$$t$$i$$u_i$$i$$x$$y$$z$ ke formula yang menangkap implikasinya ( x → ( y ∨ z ) ) , memaksakan bahwa x hanya bisa benar jika salah satu dari anak-anaknya benar. Untuk menyelesaikan rumus, tambahkan klausa tunggal yang mengatakan bahwa variabel simpul akar pohon biner harus benar. Dalam penugasan kebenaran awal, nilai-nilai semua variabel untuk node internal diatur ke false, yang memenuhi semua klausa rumus kecuali untuk klausa tunggal yang membutuhkan simpul akar pohon untuk memiliki variabelnya benar.$(\neg x \vee y \vee z)$$(x \rightarrow (y \vee z))$$x$

Ini melengkapi deskripsi rumus dan penugasan kebenaran. Atur parameter dari masalah FLIP DISTANCE menjadi sama dengan ( k + log t + 1 ) , yang sesuai untuk komposisi silang. Tetap menunjukkan bahwa kita dapat membalik variabel k ′ untuk membuat rumus benar jika beberapa grafik input G i memiliki penutup simpul ukuran k .$k'$$(k + \log t + 1)$$k'$$G_i$$k$

Pada arah sebaliknya, misalkan memiliki penutup simpul size- k . Setel variabel k yang sesuai dengan simpul k di penutup menjadi true dengan membaliknya. Setel variabel pemilih u i menjadi true untuk menyandikan bahwa input i diaktifkan, dan balik variabel t log internal binary tree node di jalur leaf i ke root ke true. Sangat mudah untuk memverifikasi bahwa ini adalah tugas yang memuaskan: implikasi dalam pohon biner semuanya puas, nilai simpul akar disetel ke true, klausa yang memeriksa tepi G i ′ untuk $G_i$$k$$k$$k$$u_i$$i$$\log t$$i$$G_{i'}$ tetap puas karena u i ′ tetap salah, sedangkan klausa untuk graf G saya puas karena untuk setiap sisi kita setel paling tidak satu titik akhir menjadi true.$i' \neq i$$u_{i'}$$G_i$

Untuk arah maju, misalkan rumus dapat dipenuhi dengan membalikkan paling banyak variabel . Maka kita harus membalik variabel simpul root ke true. Implikasi dalam pohon biner menegakkan bahwa setidaknya satu variabel pemilih daun disetel ke true, katakan u i . Untuk memenuhi implikasi dikodekan dalam pohon biner, semua node internal pada jalan dari u i ke akar yang diatur ke benar, akuntansi untuk 1 + log t membalik. Karena u i disetel ke true, klausa yang dibuat untuk grafik G i tidak puas pada literal$k + \log t + 1$$u_i$$u_i$$1 + \log t$$u_i$$G_i$ , sehingga mereka puas karena salah satu titik akhir dari setiap tepi G i disetel ke true. Karena setidaknya 1 + log t variabel dari pohon biner dibalik, paling banyak k variabel verteks dibalik menjadi true dalam solusi ini. Ini mengkodekan penutup simpul ukuran k dalam G i dan membuktikan bahwa salah satu input adalah instance-YA. Ini melengkapi buktinya.$\neg u_i$$G_i$$1 + \log t$$k$$k$$G_i$