Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas
Sebastian MüllerIddo TzameretPublished in: CoRR (2011)
Keyphrases
- average case
- worst case
- cnf formula
- average case complexity
- propositional formulas
- theorem prover
- worst case analysis
- np complete
- uniform distribution
- max sat
- computational complexity
- first order logic
- knowledge compilation
- upper bound
- conjunctive normal form
- propositional logic
- sat problem
- lower bound
- truth assignment
- np hard
- randomly generated
- optimal solution