NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly.
Harry BuhrmanJohn M. HitchcockPublished in: Electron. Colloquium Comput. Complex. (2008)
Keyphrases
- np hard
- decision problems
- np complete
- computational complexity
- approximation algorithms
- special case
- scheduling problem
- conjunctive queries
- np hardness
- worst case
- lower bound
- integer programming
- closely related
- constraint satisfaction problems
- optimal solution
- learning algorithm
- minimum cost
- linear programming
- search algorithm
- data complexity
- databases
- set cover