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...
| Publié dans: | Journal of the ACM 51, 2 (2004). |
|---|---|
| Auteur principal: | |
| Format: | Article |
| Langue: | English |
| Sujets: |