Witnesses for non-satisfiability of dense random 3CNF formulas.

Uriel Feige Jeong Han Kim Eran Ofek

Published in: FOCS (2006)

Keyphrases

cnf formula
np complete
sat problem
randomly generated
max sat
conjunctive normal form
davis putnam
propositional formulas
truth assignment
knowledge compilation
satisfiability problem
propositional logic
phase transition
constraint satisfaction problems
np hard
relational databases
objective function