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...

Cur síos iomlán

Sonraí bibleagrafaíochta

Foilsithe in:	Journal of the ACM 51, 2 (2004).
Príomhchruthaitheoir:	Atserias, Albert
Formáid:	Alt
Teanga:	English
Ábhair:	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.