Unprovability of strong complexity lower bounds in bounded arithmetic.
Jiatu LiIgor Carboni OliveiraPublished in: Electron. Colloquium Comput. Complex. (2023)
Keyphrases
- lower bound
- worst case
- upper bound
- complexity measures
- branch and bound algorithm
- computational complexity
- vc dimension
- np hard
- data sets
- complexity analysis
- database
- special case
- computational cost
- data structure
- objective function
- np complete
- lower and upper bounds
- network flow
- quadratic assignment problem
- lower bounding