Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MAXIMUM INDEPENDENT SET:
Reports tagged with maximum independent set:
TR06-043 | 22nd March 2006
Eran Ofek, Uriel Feige

#### Random 3CNF formulas elude the Lovasz theta function

Let $\phi$ be a 3CNF formula with n variables and m clauses. A
simple nonconstructive argument shows that when m is
sufficiently large compared to n, most 3CNF formulas are not
satisfiable. It is an open question whether there is an efficient
refutation algorithm that for most such formulas proves ... more >>>

ISSN 1433-8092 | Imprint