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

Descrizione completa

Dettagli Bibliografici
Pubblicato in:Journal of the ACM 51, 2 (2004).
Autore principale: Atserias, Albert
Natura: Articolo
Lingua:English
Soggetti: