Iterated lower bound formulas: a diagonalization-based approach to proof complexity.
Rahul SanthanamIddo TzameretPublished in: STOC (2021)
Keyphrases
- lower bound
- worst case
- upper bound
- branch and bound algorithm
- objective function
- lower and upper bounds
- branch and bound
- np hard
- computational complexity
- complexity analysis
- theorem prover
- upper and lower bounds
- complete axiomatization
- decision problems
- optimal solution
- optimal strategy
- knowledge base
- lower bounding
- competitive ratio