An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle
Jan KrajícekPavel PudlákAlan R. WoodsPublished in: Electron. Colloquium Comput. Complex. (1994)
Keyphrases
- lower bound
- upper bound
- objective function
- branch and bound algorithm
- exponential size
- optimal solution
- worst case
- average case complexity
- sufficiently accurate
- constant factor
- running times
- lower and upper bounds
- computational complexity
- branch and bound
- combinatorial optimization
- polynomial size
- depth map
- data structure