NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications.
Joshua A. GrochowPublished in: CoRR (2016)
Keyphrases
- np hard
- np complete
- approximation algorithms
- provably correct
- high dimensional
- scheduling problem
- linear programming
- lower bound
- greedy heuristic
- minimum cost
- special case
- decision problems
- sparse coding
- constraint satisfaction problems
- integer programming
- worst case
- set cover
- computationally hard
- sparse matrix
- database