文章基本信息

标题：Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques
本地全文：下载
作者：Amin Coja-Oghlan ; Andreas Goerdt ; André Lanka 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：It is known that random k-SAT formulas with at least (2^k*ln2)*n random clauses are unsatisfiable with high probability. This result is simply obtained by bounding the expected number of satisfy- ing assignments of a random k-SAT instance by an expression tending to 0 when n, the number of variables tends to infinity. This argument does not give us an efficient algorithm certifying the unsatisfiability of a given random instance. For even k it is known that random k-SAT in- stances with at least Poly(logn)*n^(k/2) clauses can be efficiently certified as unsatisfiable. For k = 3 we need at least n^((3/2)+epsilon) random clauses. In case of even k we improve the aforementioned results in two ways. There exists a constant C such that 4-SAT instances with at least C*n^2 clauses can be efficiently certified as unsatisfiable. Moreover, we give a satisfiability algorithm which runs in expected polynomial time over all k-SAT instances with C*n^(k/2) clauses. Our proofs are based on the direct application of known approximation algorithms on the one hand, and on a recent estimate of the theta-function for random graphs with a linear number of edges, on the other hand.
关键词：Approximation Techniques , Max-Cut , MIN-BISECTION , Random k-SAT , satisfiability , Semidefinite programming