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

Question

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?

Answer 1

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.

Answer 2

Your understanding is correct at a very high level. A problem being in NP means that the problem is “easy” (in a certain specific sense), whereas a problem being NP-hard means that the problem is “difficult” (in another specific sense), and I think that you understand this correctly.

However, your understanding is misled in several ways.

First, a problem being in NP and a problem being NP-hard are not mutually exclusive. When a problem is both in NP and NP-hard, we say that the problem is NP-complete, as Dave Clarke explained.

Second, it is not known (or believed) that all problems in NP can be solved deterministically in time O(2ⁿ), or in time 2^O(n) for that matter. What is known is that all problems in NP can be solved deterministically in time 2^poly(n) (= 2^nO(1)). Time 2^poly(n) is often called “exponential time” in complexity theory, but note that the same term “exponential time” can sometimes also refer to time 2^O(n).

By the way, while you are right in that the traveling salesperson problem (TSP) is NP-hard, it seems that you are implying that TSP is not in NP. This point deserves some attention.

The TSP defined as a search problem (“Given a weighted directed graph, find a Hamiltonian circuit with the minimum total weight”) indeed cannot be in NP because by definition, NP is a class of decision problems. However, a natural decision version of TSP (“Given a weighted directed graph and a threshold K, decide whether the given graph has a Hamiltonian circuit with the total weight at most K”) is in NP, and this decision version is sometimes also called the traveling salesperson problem. This practice of calling the search version and the decision version by the same name is often convenient, but because of this, a strange thing happens—some people say “TSP is NP-complete” while others say “TSP is not in NP by definition,” and both are correct. See my post on math.stackexchange.com for more about this convention in general.

Answer 3

There are many exceptions to your running time summaries.

Probably most notably, TSP can be solved in $n^22^n$ time with dynamic programming (the Held-Karp Algorithm); you don't need all $n!$.

There are some NP-hard problems that can even be solved a bit faster than $2^n$. Subset sum can be solved in $O(2^{n/2})$ time, or about $O(1.4^n)$. There are many other NP-hard problems that can be solved in $c^n$ time with $c < 2$.

Some NP-hard problems, like Partition, are only "weakly NP-hard", and have pseudopolynomial solutions. This means that there is running time that's polynomial in the value of the inputs (so if the largest item in the set has size $m$, the running time is proportional to $m$ as well as the size of the set $n$). Equivalently, these problems can be solved in polynomial time if the input is given in unary. Most problems similar to Partition (like Knapsack) fall into this category, as well as many--but not all--NP-hard scheduling problems. Depending on the problem instance, this may be better than $2^n$, or even polynomial.

Graph isomorphism is in NP but is likely not NP-hard and can be solved in $O(2^{\sqrt{n\log n}})$ time (not great but better than $2^n$). Some problems that are in NP but are not known to be NP-hard can be solved more quickly. For example, factoring, which can be solved in $e^{(64n/9)^{1/3}(\log n)^{2/3}}$ time for an n-digit number using the general number field sieve.

There are several other factors that may make an NP-hard problem considered to be more or less difficult compared to others, such as how closely they can be approximated in polynomial time.