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). |
|---|---|
| मुख्य लेखक: | |
| स्वरूप: | लेख |
| भाषा: | English |
| विषय: |