Formula CNF Setara Terpendek

Biarkan menjadi Formula CNF yang memuaskan dengan variabel dan klausaBiarkan S F 1 menjadi ruang solusi F 1 .$F_1$$n$$m$$S_{F_1}$$F_1$

Pertimbangkan masalah penentuan, mengingat , Formula F 2 CNF lainnya dengan set variabel yang sama dengan F 1 , dengan S F 2 = S F 1 (ruang solusi yang sama dengan F 1 ), tetapi dengan klausa sesedikit mungkin ( satu-satunya tujuan adalah untuk meminimalkan jumlah klausa, jadi berapa literal yang mungkin dimiliki setiap klausa tidak relevan).$F_1$$F_2$$F_1$$S_{F_2} = S_{F_1}$$F_1$

Pertanyaan

Adakah yang sudah menyelidiki masalah ini? Apakah ada hasil dalam literatur tentang hal itu?

Sebagai contoh, pertimbangkan CNF Formula (setiap baris adalah klausa): $F_1$

x 2 ∨ x 3 ∨ x 4 ¬ x 1 ∨ x 2 ∨ x 4 ¬ x 1 ∨ x 2 ∨ ¬ x 3 ¬ x 1 ∨ x 3 ∨ x 5 ¬ x 1 ∨ x 2 ∨ ¬ x $x_1 \lor x_2 \lor x_3$
$x_2 \lor x_3 \lor x_4$
$\lnot x_1 \lor x_2 \lor x_4$
$\lnot x_1 \lor x_2 \lor \lnot x_3$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2 \lor \lnot x_5$

dan rumus berikut : $F_2$

x 2 ∨ x 3 ∨ x 4 ¬ x 1 ∨ x 3 ∨ x 5 ¬ x 1 ∨ x $x_1 \lor x_2 \lor x_3$
$x_2 \lor x_3 \lor x_4$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2$

keduanya memiliki ruang solusi yang sama, tetapi sementara memiliki 6 klausa, F 2 hanya memiliki 4 . $F_1$$6$$F_2$$4$

Akhirnya, pertimbangkan rumus berikut : $F_3$

¬ x 1 ∨ x 3 ∨ x 5 ¬ x 1 ∨ x $x_2 \lor x_3$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2$

Ruang solusi sekali lagi sama, tetapi hanya dengan klausa.$3$

Masalah menentukan apakah ada rumus CNF yang setara dengan paling banyak jumlah literal yang diberikan adalah -complete. Versi yang meminimalkan jumlah klausa berada dalam faktor n dari ukuran rumus, di mana n adalah jumlah variabel. Lihat bagian 6 dari:$\Pi_2^p$$n$$n$

• Christopher Umans, Masalah DNF Setara Minimum dan Implan Terpendek , JCSS 63 (4), 597–611, 2001. doi: 10.1006 / jcss.2001.1775 ( pracetak )

Hasil terbaru menunjukkan bahwa menghitung batas bawah tertentu untuk ukuran rumus CNF setara terpendek (diukur dengan jumlah klausa, seperti yang Anda tentukan) adalah NP-complete. Makalah ini juga menyatakan bahwa masalah Anda dalam meminimalkan jumlah klausa adalah -lengkap juga, mengutip makalah Umans di atas, meskipun mengapa hal berikut ini tidak segera jelas bagi saya.$\Pi^p_2$

• Ondřej Čepek, Petr Kučera dan Petr Savický, Boolean berfungsi dengan sertifikat sederhana untuk kompleksitas CNF , DAM 160 (4–5), 365–382, 2012. doi: 10.1016 / j.dam.2011.05.013

Masalah miniisasi rangkaian tidak dapat dipecahkan (lihat komentar di bawah). Apa yang saya pikir Anda mungkin tertarik adalah teknik beberapa pemecah SAT berlaku (setidaknya sampai tingkat tertentu) yang disebut SAT preprocessing. Misalnya pemecah MiniSAT yang terkenal menggunakan Minelite minimizer CNF untuk memproses ulang sebuah instance. Google Cendekia memberikan banyak hasil untuk "sat preprocessing" juga.

solusi std / dikenal utama untuk minimisasi CNF di EE adalah algoritma Quine-McCluskey yang ada banyak implementasi, beberapa domain publik. Namun pemahaman saya adalah bahwa (tidak disebutkan dalam artikel wikipedia saat ini) paling kembali ke heuristik dan algoritma serakah untuk menemukan solusi esp untuk formula besar, yaitu mereka tidak perlu. temukan solusi optimal esp. untuk instance input besar.

Quine-MCluskey adalah generalisasi bekerja dengan peta Karnough yang diagramnya dapat berhasil untuk contoh kecil.

dan perhatikan bahwa mungkin ada beberapa solusi optimal dalam hal rumus setara dengan ukuran klausa (minimal) yang sama, ini akan ditunjukkan dalam referensi yang baik pada Subj. menemukan minimum tampaknya mengurangi daftar semua implikasi utama yang dapat melibatkan ledakan eksponensial besar dalam memori / "ruang" dibandingkan dengan ukuran formula asli.