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

ver descrição completa

Detalhes bibliográficos

Publicado no:	Journal of the ACM 51, 2 (2004).
Autor principal:	Atserias, Albert
Formato:	Artigo
Idioma:	English
Assuntos:	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.