Formula 3-CNF Minimum yang Tidak Memuaskan

Saat ini saya tertarik untuk memperoleh (atau membangun) dan mempelajari formula 3-CNF yang tidak memuaskan, dan berukuran minimum. Artinya, mereka harus terdiri dari klausa sesedikit mungkin (m = 8 lebih disukai), dan sesedikit mungkin variabel yang berbeda (n = 4 atau lebih), sehingga menghapus setidaknya satu klausa akan membuat formula memuaskan.

Secara lebih formal, formula 3-CNF F apa pun yang memenuhi syarat harus memenuhi ketentuan berikut:

F tidak memuaskan
F memiliki jumlah minimum (4+) variabel yang berbeda (atau negasinya)
F memiliki jumlah minimum klausa (8+)
setiap subset F yang tepat dapat dipenuhi (memungkinkan penghapusan klausa atau klausul sewenang-wenang)
F tidak memiliki 2 klausa yang dapat direduksi menjadi klausa 2-CNF misalnya (i, j, k) & (i, j, ~k)TIDAK diizinkan (mereka mengurangi menjadi (i,j))

Misalnya, dengan n = 4, ada banyak rumus minimal 8-klausul 3-CNF yang tidak memuaskan. Pertama, dengan melihat 4-hypercube dan mencoba menutupinya dengan pinggiran (2-wajah), seseorang dapat membuat formula yang tidak memuaskan berikut:

1. (~A,  B,  D)
2. (~B,  C,  D)
3. ( A, ~C   D)
4. ( A, ~B, ~D)
5. ( B, ~C, ~D)
6. (~A,  C, ~D)
7. ( A,  B,  C)
8. (~A, ~B, ~C)

Ini memenuhi syarat sebagai formula 3-CNF minimum yang tidak memuaskan karena:

Tidak memuaskan:
- Klausa 1-3 setara dengan: D or A=B=C
- Klausa 4-6 setara dengan: ~D or A=B=C
- Mereka menyiratkan A=B=C, tetapi dengan klausul 7 dan 8, ini adalah kontradiksi.
Hanya ada 4 variabel berbeda.
Hanya ada 8 klausa.
Menghapus klausa apa pun menjadikannya memuaskan.
Tidak ada 2 klausa yang 'dapat direduksi' menjadi klausa 2-CNF.

Jadi saya kira pertanyaan keseluruhan saya di sini adalah, menurut kepentingannya:

Apa sajakah rumus minimum kecil lainnya yang memenuhi kondisi di atas? (Yaitu untuk mengatakan, 4,5,6 variabel dan 8,9,10 klausa)
Apakah ada semacam database atau "atlas" dari formula minimum seperti itu?
Algoritma nonrandom apa yang ada untuk membangunnya secara langsung, jika ada?
Apa saja wawasan tentang karakteristik formula ini? Bisakah mereka dihitung atau diperkirakan, diberikan n (# variabel) dan m (# klausa)?

Terima kasih sebelumnya atas balasan Anda. Saya menyambut setiap jawaban atau komentar.

cc.complexity-theory sat MAF
sumber

Setiap klausa 3-CNF melarang 1/8 dari solusi yang mungkin. Jadi jelas Anda selalu membutuhkan setidaknya 8 klausa, atau lebih jika set solusi yang ditolak tumpang tindih. Karena kondisi Anda 5 melarang solusi tidak diizinkan yang tumpang tindih untuk n = 3, Anda memerlukan lebih dari 8 klausa untuk kasus ini: perhatikan bahwa contoh Anda tidak mematuhi ketentuan 5.

András Salamon

Ya, Anda benar di semua titik, András. 8 klausa adalah persyaratan minimum untuk formula 3-CNF yang tidak memuaskan, dan karenanya kondisi 5 mungkin agak terlalu ketat untuk tujuan saya dalam mencari / membuat formula kualifikasi. Saya menyadari bahwa untuk n = 3, kondisi 5 harus selalu dilanggar, tetapi dimasukkan hanya untuk tujuan ilustrasi. Saya benar-benar tertarik pada rumus kualifikasi ukuran n = 4 + (yaitu 4 atau lebih variabel, tetapi tidak terlalu banyak.). Mungkin saya akan menggaruk kondisi 5.

MAF

Saya pikir bahwa "contoh" Anda dengan n = 3 membingungkan daripada ilustratif, karena (seperti yang ditunjukkan András dalam komentarnya) itu bukan contoh dari apa yang Anda tanyakan dalam pertanyaan ini. Contoh dengan n = 4 sangat bagus dan ilustratif. Mengapa tidak Anda hapus saja contohnya dengan n = 3?

Tsuyoshi Ito

Poin bagus, Tsuyoshi. Selesai

MAF

{x}

$\{x\}$

{x^{'}}

$\{x'\}$

C

$C$

C \cup {v}

$C \cup \{v\}$

C \cup {v^{'}}

$C \cup \{v'\}$

v

$v$

Jawaban:

$\lnot A \lor \lnot B \lor \lnot C$ $2$

$\lnot A \lor \lnot B \lor \lnot E$
$\lnot B \lor \lnot C \lor E$

$n=5$ $m=9$

$l_1 \lor l_2 \lor l_3$ $2$

$l_1 \lor l_2 \lor v$
$l_2 \lor l_3 \lor \lnot v$

$v$ $n$ $m$ $1$ $r=\frac{m}{n}$ $1$ $n$ $r=1$

Giorgio Camerani
sumber

Terima kasih atas jawabannya, Walter. Prosedur yang Anda gambarkan sangat membantu memang untuk menghasilkan formula min 'unsat' yang bahkan sedikit lebih besar, yaitu, begitu Anda memiliki kumpulan inti yang Anda temukan memiliki sifat yang menarik.

MAF

@ MAF: Terima kasih kembali. Terima kasih telah mengirim pertanyaan yang begitu menarik.

Giorgio Camerani

Saya percaya kondisi nomor 5 tidak benar-benar dipegang oleh contoh Anda dan tidak dapat dipegang sebelumnya.
Biarkan klausa berikut ini menjadi setara:

( p, q) = (~A,B,D)(A,~B,~D)

Yang akan memungkinkan kita untuk memetakan klausa A, B, C, dan D ke variabel baru p, q, r, dan s sebagai tabel kebenaran berikut:

A B C D | p q r s
-----------------
0 0 0 0 | 0 1 0 0
0 0 0 1 | 0 1 0 1
0 0 1 0 | 0 1 1 0
0 0 1 1 | 0 1 1 1
-----------------
0 1 0 0 | 1 0 0 0
0 1 0 1 | 0 0 0 0
0 1 1 0 | 1 0 0 1
0 1 1 1 | 0 0 0 1
-----------------
1 0 0 0 | 0 0 1 0
1 0 0 1 | 1 0 1 0
1 0 1 0 | 0 0 1 1
1 0 1 1 | 1 0 1 1
-----------------
1 1 0 0 | 1 1 0 0
1 1 0 1 | 1 1 0 1
1 1 1 0 | 1 1 1 0
1 1 1 1 | 1 1 1 1
-----------------

Dan sekarang kita dapat mengekspresikan klausa A, B, C, dan D dalam hal p, q, r, dan s:

1. (~A,  B,  D) = ( p, q,~r, s)( p, q,~r,~s)
2. (~B,  C,  D) = (~p, q, r, s)(~p,~q, r, s)
3. ( A, ~C   D) = ( p,~q,~r, s)(~p, q, r,~s)
4. ( A, ~B, ~D) = ( p, q, r, s)( p, q, r,~s)
5. ( B, ~C, ~D) = ( p,~q,~r,~s)(~p, q,~r,~s)
6. (~A,  C, ~D) = (~p, q,~r, s)(~p,~q, r,~s)
7. ( A,  B,  C) = ( p,~q, r, s)( p,~q, r,~s)
8. (~A, ~B, ~C) = (~p,~q,~r, s)(~p,~q,~r,~s)

Karena semua klausa ditunjukkan dan dihubungkan dengan klausa A, B, C, dan D. Kemudian kita dapat mengklaim bahwa klausa p, q, r, dan s dapat direduksi menjadi:

( p, q, r)
( p, q,~r)
( p,~q, r)
( p,~q,~r)
(~p, q, r)
(~p, q,~r)
(~p,~q, r)
(~p,~q,~r)

Yang jelas melanggar kondisi nomor 5.

Apa yang ingin saya tunjukkan adalah bahwa bahkan contohnya tidak secara eksplisit menunjukkan bahwa ada 2 klausa yang dapat dikurangi menjadi 2-CNF, tetapi secara implisit memiliki (misalnya (~ A, B, D) dan (A, ~ B, ~ D)), Anda mungkin tidak dapat mengekspresikan 2-CNF dengan variabel yang diberikan tetapi ketika Anda memperkenalkan pemetaan yang berbeda untuk masalah, Anda akan dapat mengekspresikannya.

Khazam Alhamdan
sumber