Formula 3-CNF yang membutuhkan lebar resolusi

Ingat bahwa lebar dari resolusi sanggahan dari formula CNF F adalah jumlah maksimal literal dalam klausul terjadi di R . Untuk setiap w , ada rumus yang tidak memuaskan F dalam 3-CNF st setiap resolusi resolusi F membutuhkan lebar setidaknya w .$R$$F$$R$$w$$F$$F$$w$

Saya membutuhkan contoh konkret dari formula yang tidak memuaskan dalam 3-CNF (sekecil dan sesederhana mungkin) yang tidak memiliki resolusi penolakan lebar 4.

Contoh berikut berasal dari makalah yang memberikan karakterisasi kombinatorial lebar resolusi oleh Atserias dan Dalmau ( Jurnal , ECCC , salinan penulis ).

Teorema 2 dari makalah ini menyatakan bahwa, diberikan rumus CNF , resolusi penolakan lebar paling banyak k untuk F sama dengan strategi memenangkan Spoiler dalam permainan kerikil eksistensial ( k + 1 ) . Ingat bahwa permainan kerikil eksistensial dimainkan antara dua pemain bersaing, disebut Spoiler dan duplikator, dan posisi permainan yang tugas parsial ukuran domain paling k + 1 ke variabel F . Dalam game ( k + 1 ) -pebble, mulai dari tugas kosong, Spoiler ingin memalsukan klausa dari $F$$k$$F$$(k+1)$$k+1$$F$$(k+1)$$F$sambil mengingat paling banyak nilai b + pada satu waktu, dan Duplicator ingin mencegah Spoiler melakukan hal itu.$k+1$

Contohnya didasarkan pada (peniadaan) prinsip lubang pos.

Untuk setiap dan j ∈ { 1 , … , n } , misalkan p i , j menjadi variabel proposisional yang berarti bahwa merpati i duduk di lubang j . Untuk setiap i ∈ { 1 , … , n + 1 } dan j ∈ { 0 , … , n } , biarkan$i \in \{1, \dotsc, n+1 \}$$j \in \{1, \dotsc, n \}$$p_{i,j}$$i$$j$$i \in \{1, \dotsc, n+1 \}$$j \in \{0, \dotsc, n \}$ menjadi variabel proposisional baru. Berikut 3 -CNF rumus E P i mengungkapkan bahwa merpati saya duduk di beberapa lubang: E P i ≡ ¬ y i , 0 ∧ n ⋀ j = 1 ( y i , j - 1 ∨ p i , j ∨ ¬ y i , j ) ∧ y i , n$y_{i,j}$$3$${EP}_i$$i$

$${EP}_i \equiv \neg y_{i,0} \wedge \bigwedge_{j=1}^n (y_{i,j-1} \vee p_{i,j} \vee \neg y_{i,j} ) \wedge y_{i,n}.$$ Akhirnya, rumus -CNF E P H P n + 1 n yang menyatakan negasi prinsip pigeonhole adalah gabungan dari semua E P i dan semua klausa H i , j k ≡ ¬ p i , k ∨ ¬ p j , k untuk i , j ∈ { 1 , … , n + 1 } , i ≠ j dan$3$${EPHP}_n^{n+1}$${EP}_i$$H_k^{i,j} \equiv \neg p_{i,k} \vee \neg p_{j,k}$$i,j \in \{1, \dotsc, n+1 \}, i \ne j$ .$k \in \{1, \dotsc, n \}$

Lemma 6 dari makalah ini memberikan bukti yang cukup singkat dan intuitif bahwa Spoiler tidak dapat memenangkan permainan kerikil di E P H P n + 1 n , maka E P H P n + 1 n tidak memiliki resolusi resolusi lebar yang paling n - 1 .$n$${EPHP}_n^{n+1}$${EPHP}_n^{n+1}$$n-1$

Makalah ini memiliki contoh lain dalam Lemma 9, berdasarkan prinsip urutan linier padat.

Mengingat bahwa penghitungan lebar minimum untuk sanggahan resolusi adalah EXPTIME-complete, dan terlebih lagi diperlukan waktu untuk menyatakan bahwa lebar minimum setidaknya k + 1 (lihat makalah Berkholz di FOCS atau arXiv ), mungkin sulit untuk memberikan contoh yang terbukti membutuhkan penyangkalan resolusi lebar?$\Omega(n^{(k-3)/12})$$k+1$