patternMinor
What is the relationship between NP/NP-Complete/NP-Hard to time complexity?
Viewed 0 times
thewhathardtimecompletebetweencomplexityrelationship
Problem
I'm familiar with a few problems of each class and even though the definitions are based on sets and polynomial reducibility, I see a pattern with time complexity. NP problems appear to be $O(2^n)$ (minus the P problems of course), and NP-hard problems seem to be worse: $n^n$ or $n!$ (Chess, TSP). Is this a misleading interpretation?
Solution
See the definition of NP completeness. For a problem to be NP-complete, it
Condition 2 alone is what it means to be NP hard. Thus NP complete problems are the intersection of NP problems and NP hard problems.
NP $\subseteq$ EXPTIME, thus NP problems can be solved in $2^{O(p(n))}$, for some polynomial $p(n)$. But it is well know that if P $=$ NP, then NP problems can be solved in polynomial time.
NP hard problems are at least as hard as NP problems – you cite a few examples.
- needs to be in NP and
- all NP problems need to be reducible to it in polynomial time.
Condition 2 alone is what it means to be NP hard. Thus NP complete problems are the intersection of NP problems and NP hard problems.
NP $\subseteq$ EXPTIME, thus NP problems can be solved in $2^{O(p(n))}$, for some polynomial $p(n)$. But it is well know that if P $=$ NP, then NP problems can be solved in polynomial time.
NP hard problems are at least as hard as NP problems – you cite a few examples.
Context
StackExchange Computer Science Q#5009, answer score: 8
Revisions (0)
No revisions yet.