Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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