Seberapa banyak kita dapat mengurangi jumlah klausa dengan mengkonversi dari

Jika kita mengira bahwa kita mulai dengan turunan dari -SAT, dan mencoba mengonversi masalah menjadi turunan dari -SAT, di mana terdapat literal per klausa, dapatkah kami menjamin pengurangan dalam jumlah klausa total?$k$$(k+m)$$(k+m)$

Saya menyadari setelah memposting bahwa kami tidak dapat menjamin bahwa jumlah klausa dapat dikurangi. Namun, saya bertanya-tanya apakah kita memiliki klausa, dapatkah kita mendapatkan sesuatu seperti klausa dengan beberapa teknik "reduksi"?$n$$n/k + O(1)$

Jika demikian, seberapa banyak kita dapat menjamin jumlah klausa dapat dikurangi? Misalnya, jika kita mulai dengan -SAT dengan klausa , berapakah terkecil yang dijamin , jumlah klausa baru, yang akan dihasilkan jika kita mengonversi instance ini ke -SAT?$k$$n_k$$n_{k+m}$$(k+m)$

Lebih penting lagi, bagaimana kita melakukan konversi ini?

Salah satu jenis konversi hanyalah kebalikan dari konversi k-sat-to-3-sat:

Ingat, konversi k-sat ke "j" -sat, $j<k$:

Sini, $d$adalah variabel dummy, yang artinya sekitar "Klausa ini tidak benar, tetapi klausa lain yang saya tahu adalah". Klausa lain menjadi klausa berikutnya yang terpisah dari aslinya. Di atas adalah contoh di mana$2j \geq k$, jika tidak, simpul split 2 masih akan lebih besar dari $j$, dan kita harus membaginya lagi, dengan cara yang sama.

Membalikkan konversi

$(x_1 \vee x_2 ... x_j) \wedge (\overline x_j \vee x_{j+1} \vee ... x_k)$ maka Anda dapat menggabungkan klausa menjadi:

$(x_1 \vee x_2 ... x_{j-1} \vee x_{j+1} \vee x_{j+2} \vee ... x_k)$

Perhatikan yang hilang $x_j$ dalam formula baru ini.

Tentu saja, Anda tidak dijamin menemukan klausa seperti ini dalam formula sewenang-wenang sehingga dijamin terkecil$n_{k+m}$ adalah sama dengan $n_k$.

Namun, pada rumus biasa, variabel dan negasinya akan muncul dalam rumus; jika tidak, Anda dapat melakukan eliminasi literal murni (dijelaskan di sini ). Untuk kesederhanaan, mari kita asumsikan juga$k+m \geq 2k-2$. Lalu kita bisa menggabungkan dua klausa yang mengandung literal dalam satu dan negasi di yang lain. Karena setiap literal harus memiliki klausa lain dengan negasi, orang dapat secara empiris menebak bahwa Anda seharusnya dapat mengurangi kira-kira separuh jumlah klausa (Anda mungkin terjebak dengan beberapa literal dan negasinya dalam klausa yang sudah tergabung, dan dengan demikian Anda akan terjebak dengan klausa beberapa klausa yang tidak dapat disatukan pada akhirnya; bergabung secara optimal dengan klausa seperti ini mungkin merupakan masalah lain yang menarik).

EDIT:

Setelah refleksi, saya menyadari itu $x_j$harus bebas dan tidak digunakan di tempat lain dalam rumus untuk menutup dua klausa yang menjadi miliknya. Oleh karena itu, klausa jenis ini (satu mengandung literal, dan yang lainnya negasi, dengan literal ini tidak digunakan di tempat lain dalam formula) jauh lebih jarang daripada yang saya pikir sebelumnya di atas. Jadi jawaban sebenarnya adalah, tidak ada jaminan berapa banyak kita bisa mengurangi jumlah klausa dalam formula.