Kasus mudah SAT yang tidak mudah untuk resolusi pohon

Adakah kelas formula CNF alami - lebih disukai yang sebelumnya telah dipelajari dalam literatur - dengan sifat-sifat berikut:$C$

• adalah kasus yang mudah dari SAT, seperti misalnya Horn atau 2-CNF, yaitu, keanggotaan dalam C dapat diuji dalam waktu polinomial, dan rumus F ∈ C dapat diuji untuk kepuasan dalam waktu polinomial.$C$$C$$F\in C$
• Rumus yang tidak memuaskan tidak diketahui memiliki penyangkalan resolusi pohon-pendek seperti (ukuran polinomial). Yang lebih baik lagi adalah: ada rumus-rumus yang tidak memuaskan di dalam C yang diketahui batas bawahnya yang super polinomial untuk resolusi mirip pohon.$F\in C$$C$
• Di sisi lain, formula yang tidak memuaskan dalam diketahui memiliki bukti pendek dalam beberapa sistem bukti yang lebih kuat, misalnya dalam resolusi mirip-dag atau sistem yang bahkan lebih kuat.$C$

tidak boleh terlalu jarang, yaitu, mengandung banyak formula dengan n variabel, untuk setiap (atau setidaknya untuk sebagian besar nilai-nilai) n ∈ N . Itu juga harus non-sepele, dalam arti mengandung formula yang memuaskan dan tidak memuaskan.$C$$n$$n\in \mathbb{N}$

Pendekatan berikut untuk menyelesaikan rumus CNF acak harus bermakna: temukan penugasan sebagian α st rumus sisa F α di C , dan kemudian terapkan algoritma waktu polinomial untuk rumus dalam C hingga F α . Oleh karena itu saya ingin jawaban lain selain kendala yang semuanya berbeda dari jawaban yang saat ini diterima, karena saya pikir jarang bahwa rumus arbitrer akan menjadi kendala yang sama sekali berbeda setelah menerapkan batasan.$F$$\alpha$$F\alpha$$C$$C$$F\alpha$

Sepertinya Anda tertarik pada semua kendala yang berbeda (dan kalimat terakhir Anda ada di jalur yang benar). Ini adalah contoh non-sepele prinsip pigeonhole, di mana jumlah merpati belum tentu lebih besar dari jumlah lubang, dan di samping itu beberapa merpati mungkin dilarang dari beberapa lubang.

Semua kendala yang berbeda dapat diputuskan dengan mencocokkan waktu polinomial tingkat rendah.

• Jean-Charles Régin, Sebuah algoritma penyaringan untuk kendala perbedaan dalam CSP , AAAI 1994, 362-367.
• DE Knuth dan A. Raghunathan, Masalah perwakilan yang kompatibel , SIAM J. Discrete Math. 5 422–427, 1992. doi: 10.1137 / 0405033

Ketika semua kendala yang berbeda dinyatakan (menggunakan salah satu dari beberapa pengkodean) sebagai instance SAT, maka pembelajaran klausa yang digerakkan konflik biasanya dengan cepat menemukan solusi jika ada. Namun, resolusi murni untuk PHP harus membangun satu set klausa superpolynomially besar untuk menunjukkan bahwa contoh tersebut tidak memuaskan. Ikatan ini jelas berlaku untuk masalah yang lebih umum ini. Di sisi lain, ingatlah bahwa penyandian Cook terhadap PHP memungkinkan penolakan resolusi yang diperluas dengan ukuran polinomial .

• SA Cook, Bukti singkat tentang prinsip lubang merpati menggunakan resolusi yang diperluas , SIGACT News 8 28–32, 1976. doi: 10.1145 / 1008335.1008338

Karya terbaru di sepanjang baris ini adalah Bab 5 dari tesis Sergi Oliva , yang membentuk dasar sebuah makalah dengan Alberto Atserias di CCC 2013.

Saya harap Anda mengetahui hasil klasik Cook, jadi mungkin Anda bermaksud membatasi kekuatan sistem bukti dalam kondisi ketiga Anda?

Saya tidak yakin mengapa orang juga memerlukan rumus sat tetapi ada beberapa artikel tentang pemisahan antara resolusi Umum dan Pohon misalnya [1]. Kedengarannya bagi saya bahwa inilah yang Anda inginkan.

[1] Ben-Sasson, Eli, Russell Impagliazzo, dan Avi Wigderson. "Dekat pemisahan optimal seperti pohon dan resolusi umum." Combinatorica 24.4 (2004): 585-603.

Anda mungkin tertarik pada rumus SAT dengan "bandwidth" atau "treewidth" kecil (logarythmic). Rumus ini secara rekursif dapat dipartisi sedemikian rupa sehingga batas komunikasi antara partisi kecil, dan oleh karena itu pendekatan pemrograman dinamis enumeratif dapat digunakan untuk menyelesaikannya. Topik itu populer di tahun sembilan puluhan. Saya pernah menghitung dengan tepat jumlah siklus hamiltonian dalam grafik treewidth kecil dari 24.000 simpul, jadi masalah #P dengan treewidth kecil juga dapat dipecahkan. Bodlaender adalah referensi utama.

makalah berikut ini sepertinya dekat dengan apa yang diminta dalam beberapa hal (jika tidak cocok mungkin JJ dapat menjelaskan mengapa). pertanyaannya ingin mengesampingkan instance PHP (pigeonhole) berdasarkan pada kurangnya formula benar / salah, tetapi (sebagaimana dikutip dalam jawaban lain) PHP adalah salah satu generator case / instance yang paling banyak dipelajari dari sisi teori dan memiliki selalu menjadi generator untuk formula yang memuaskan / tidak memuaskan meskipun formula yang memuaskan kurang ditekankan / dipelajari.

${^m_n}$$m$$n$$m>n$$m \leq n$

• Resolusi Pohon-Seperti Superpolynomially Lebih lambat daripada Resolusi Seperti-DAG untuk Prinsip Pigeonhole (1999) oleh Kazuo Iwama, Shuichi Miyazaki

pendekatan lain adalah pergi dalam sudut yang lebih empiris dan hanya menghasilkan contoh acak (mungkin sekitar 50% titik transisi yang mudah-sulit-mudah memuaskan) dan menyaringnya agar sesuai dengan kriteria yang dinyatakan. seseorang akan membutuhkan implementasi resolusi pohon / resolusi DAG atau "sistem yang lebih kuat".