Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Random k-SAT:
TR03-030 | 27th February 2003
Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich

Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques

Abstract. 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 ... more >>>

ISSN 1433-8092 | Imprint