Tautologie / sprzeczności średnich przypadków, poza przypadkowym modelem k-CNF

16

Jest dobrze wiadomo, że losowy Preparaty -cnf na n zmiennymi c n klauzule unsatisfiable (tj sprzeczności), z dużym prawdopodobieństwem, na wystarczająco dużej stałej C . Tak więc losowe formuły k- CNN (dla c wystarczająco dużych) stanowią naturalny rozkład w niezadowalających formułach boolowskich (lub podwójnie w tautologiach, tj. Negacjach sprzeczności). Ten rozkład został dokładnie zbadany.kndondokdo

Moje pytanie jest następujące : czy istnieją inne ustalone rozkłady zdań tautologii lub sprzeczności zdań, które można uznać za uchwycenie „przeciętnego przypadku” tautologii lub niezadowalających wzorów? Czy te rozkłady były intensywnie badane?

cc.complexity-theory reference-request lo.logic sat random-k-sat Iddo Tzameret
źródło
1
@Iddo Tautologie nie istnieją w „prawdziwym” modelu CNF, ponieważ w przeciwnym razie musiałbyś mieć literał i jego dopełnienie w tej samej klauzuli… Tautologie nie są interesujące do studiowania w CNF.
Tayfun Pay
1
@ Pay, negacja niezadowalającej formuły jest oczywiście tautologią. Dlatego też możemy rozważyć losowe k-CNF jako rozkład między tautologiami (gdy stosunek klauzuli do zmiennej jest wystarczająco duży i gdzie istnieje prawdopodobieństwo o (1), aby k-CNF był zadowalający).
Iddo Tzameret
1
Myślę, że Tayfun ma rację. Powinieneś mówić o tym, że albo formuły CNF są niezadowalające, albo formuły DNF będące tautologiami. W bieżącym pytaniu łączysz oba.
Tsuyoshi Ito
1
To mój ostatni komentarz w tej sprawie: nie wiem, dlaczego nalegasz, aby zachować słowo „tautologie”, co jest wyraźnie błędne, jak wyjaśnił Tayfun. Ale nic mi nie jest, jeśli nie chcesz uwzględniać komentarzy innych osób, aby poprawić brzmienie twojego pytania.
Tsuyoshi Ito
3
Wolę zachować w tytule termin „tautologie”, ponieważ pytam o dystrybucje dotyczące tautologii lub sprzeczności, a pytanie jest odpowiednio sformułowane.
Iddo Tzameret,

Odpowiedzi: