Tautologi / kontradiksi kasus rata-rata, di luar model k-CNF acak

16

Sudah diketahui bahwa rumus acak -CNF atas variabel dengan klausa tidak memuaskan (yaitu mereka kontradiksi) dengan probabilitas tinggi, untuk konstanta yang cukup besar . Dengan demikian, rumus acak -CNF (untuk cukup besar) merupakan distribusi alami atas formula Boolean yang tidak memuaskan (atau setiap akhir, lebih dari tautologi, yaitu negasi kontradiksi). Distribusi ini telah dipelajari secara luas.n c n ckncnckc

Pertanyaan saya adalah sebagai berikut : apakah ada distribusi mapan lainnya atas tautologi atau kontradiksi proposisional, yang dapat dianggap sebagai menangkap "kasus rata-rata" dari tautologi atau formula yang tidak memuaskan? Apakah distribusi ini telah dipelajari secara intensif?

cc.complexity-theory reference-request lo.logic sat random-k-sat Iddo Tzameret
sumber
1
@Iddo Tautologies tidak ada dalam model CNF "benar" karena jika tidak, Anda perlu memiliki literal dan pelengkap dalam klausa yang sama .... Tautologi tidak menarik untuk dipelajari di CNF.
Tayfun Bayar
1
@Pay, negasi formula yang tidak memuaskan jelas merupakan tautologi. Oleh karena itu, kita dapat menganggap k-CNF acak sebagai distribusi atas tautologi (ketika rasio klausa-ke-variabel cukup besar, dan di mana ada probabilitas o (1) untuk k-CNF memuaskan).
Iddo Tzameret
1
Saya pikir Tayfun benar. Anda harus berbicara tentang formula CNF yang tidak memuaskan atau formula DNF sebagai tautologi. Dalam pertanyaan saat ini, Anda mencampur keduanya.
Tsuyoshi Ito
1
Ini adalah komentar terakhir saya tentang masalah ini: Saya tidak tahu mengapa Anda bersikeras untuk menjaga kata "tautologi," yang jelas-jelas salah seperti yang dijelaskan Tayfun. Tapi saya baik-baik saja jika Anda tidak ingin memasukkan komentar orang lain untuk meningkatkan kata-kata dari pertanyaan Anda.
Tsuyoshi Ito
3
Saya lebih suka menyimpan istilah 'tautologi' dalam judul karena saya bertanya tentang distribusi pada tautologi atau kontradiksi, dan pertanyaannya diutarakan sesuai.
Iddo Tzameret

Jawaban:

4

Paul Beame memiliki dua makalah (dengan berbagai penulis pendamping) di mana kompleksitas resolusi distribusi tertentu dari rumus acak dipelajari. Rumus-rumus ini muncul dengan menyatakan sifat-sifat, seperti k-colorability atau memiliki set ukuran k yang independen, dari grafik acak dari distribusi biasa ( n , p ) . Inilah tautannya:G(n,p)

Paul Beame, Russell Impagliazzo, dan Ashish Sabharwal. Kompleksitas resolusi set independen dan penutup simpul dalam grafik acak. Kompleksitas Komputasi, 16 (3): 245-297, 2007.

Paul Beame, Joe Culberson, David Mitchell, dan Cristopher Moore. Kompleksitas resolusi grafik acak k-colorability. Matematika Terapan Diskrit, 153: 25-47, 2005.

Jan Johannsen
sumber