Lower Bound on Hilbert's Nullstellensatz and propositional proofs
Paul BeameRussell ImpagliazzoJan KrajícekToniann PitassiPavel PudlákPublished in: FOCS (1994)
Keyphrases
- lower bound
- upper bound
- first order logic
- branch and bound algorithm
- theorem proving
- branch and bound
- theorem prover
- propositional logic
- objective function
- lower and upper bounds
- np hard
- lower bounding
- worst case
- optimal solution
- formal proof
- proof procedure
- sufficiently accurate
- equational theories
- multi valued
- default logic
- formal proofs
- competitive ratio
- polynomial approximation
- upper and lower bounds
- sample complexity
- satisfiability testing