What is the relationship between NP/NP-Complete/NP-Hard to time complexity?

Problem Detail: 

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?

Asked By : sdfasdgasg

Answered By : Dave Clarke

See the definition of NP completeness. For a problem to be NP-complete, it

1. needs to be in NP and
2. 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/5009