Adakah hasil pada biner boolean CSP di luar traktabilitas parameter tetap dari masalah hampir 2SAT?

Biarkan menjadi rumus 2CNF dan bilangan bulat tidak negatif. Hal ini terbukti dalam kertas bahwa masalah memutuskan apakah seseorang dapat menghapus paling klausul untuk membuat satisfable, tetap-parameter penurut, di mana adalah parameter. Pertanyaan saya adalah apakah ada beberapa pekerjaan yang menggeneralisasi hasil ini ke CSP boolean biner lainnya? (Yaitu, untuk memutuskan apakah seseorang dapat menghapus paling banyak kendala untuk membuat beberapa contoh CSP memuaskan, parameterkan oleh ) Atau hasil negatif? $\varphi$ $k$ $k$ $\varphi$ $k$ $k$ $k$

parameterized-complexity csp fixed-parameter-tractable Keteraturan
sumber

Saya benar-benar ingin tahu apa yang saya lewatkan di sini - bukankah hampir 2SAT traktat parameter tetap sepele karena hanya ada banyak set secara polinomially set paling banyak

klausa untuk

diperbaiki ?

k

$k$

k

$k$

Dave

@ Sudah ada sekitar

set klausa, tetapi traktabilitas parameter tetap tidak memungkinkan

muncul di bagian eksponensial runtime.

O (n^{k})

$O(n^k)$

k

$k$

Keteraturan

Jawaban:

Sepengetahuan saya mengklasifikasikan varian CSP ini terbuka lebar. Anda dapat mengungkapkan beberapa masalah yang dapat ditelusuri parameter-tetap dalam pengaturan (mis., D-Hitting Set kira-kira merupakan kasus di mana Anda memiliki klausa ukuran positif paling banyak di d penugasan negatif; kira-kira berarti bahwa masalah CSP sedikit lebih umum tetapi dengan mudah mengurangi kembali ke d-HS, atau setidaknya berbobot d-HS). Bahkan untuk kendala yang dapat Anda terapkan melalui rumus 2-CNF terukur yang ada, terbuka apa kompleksitasnya. Masalahnya adalah ketika menerapkan kendala dengan cara ini, sementara mereka 2-CNF, Anda hanya membayar satu untuk menghapus semuanya. Oleh karena itu bahkan kendala sederhana yang hanya merupakan gabungan dari dua lainnya dapat menjadi sulit (saya mungkin punya referensi + contoh nanti).

Stefan Kratsch
sumber