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).
المؤلف الرئيسي:	Atserias, Albert
التنسيق:	مقال
اللغة:	English
الموضوعات:	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.