5 ms·
If the input size is bounded, then the problem H can't be NP-hard unless P = NP. Proof: A decision problem H is NP-hard when for every problem L in NP, there i
by MichaelBurge 9y ago
If the input size is bounded, then the problem H can't be NP-hard unless P = NP.
Proof:
A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time reduction R from L to H.
By assumption, H has finitely many instances, so precalculate a binary lookup table T. Accessing a lookup table takes time polynomial in L's instance size, namely O(1).
The algorithm "T . R" is then a polynomial-time algorithm for H, so P = NP.
- ggggtez 9y agoCreating the look up table took non-polynomial time. Go back to school.
- zzazzdsa 9y ago2 to the billion is still constant....
- MichaelBurge 9y agoIt's irrelevant how long the lookup table took to create: P = NP if such an algorithm exists, regardless of how difficult it is for humans to find the algorithm.