On sufficient conditions for unsatisfiability of random formulas.

A descriptive complexity approach to random 3-SAT is initiated. We show that unsatisfiability of any significant fraction of random 3-CNF formulas cannot be certified by any property that is expressible in Datalog. Combined with the known relationship between the complexity of constraint satisfactio...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής

Τόπος έκδοσης:	Journal of the ACM 51, 2 (2004).
Κύριος συγγραφέας:	Atserias, Albert
Μορφή:	Άρθρο
Γλώσσα:	English
Θέματα:	Theory of computation. Analysis of algorithms and problem complexity. Nonnumerical algorithms and problems. Complexity of proof procedures. Mathematical logic and formal languages. Mathematical logic. Logic and constraint programming. Theory.