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 |
| 主题: |