All reports by Author Frank Schädlich:

__
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

Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich

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 >>>