6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ until P=?NP is resolved its basically an open question as far as lower bounds. what can be said is that NP complete problems dont require more than exponential time (upper bound) but whether they can be solved in far less time, ie P time (lower bound), is open.... $\endgroup$ – vzn Oct 11 '12 at 16:08
  • $\begingroup$ also your examples are wrong. TSP can be solved in $2^{n + o(n)}$ time using dynamic programming. $\endgroup$ – Sasho Nikolov Oct 11 '12 at 20:38
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note that $O(2^n) \neq 2^{O(n)}$! (And be careful of this abuse of notation!) $\endgroup$ – Raphael Oct 11 '12 at 7:38
  • $\begingroup$ So did I use it correctly or incorrectly? $\endgroup$ – Dave Clarke Oct 11 '12 at 11:16
  • $\begingroup$ What is ever "correct" with abuse of notation? ;) I just wanted to clarify this for the sake of the OP, who used $O(2^n)$ which is definitely wrong here. If we read $2^{O(n)}$ "correctly", it is what is wanted here (as far as I know). $\endgroup$ – Raphael Oct 11 '12 at 15:18
  • 2
    $\begingroup$ Dave, you may want to look up the definition of EXPTIME. The inclusion you write is correct (by enumerating certificates) but the phrase after "thus" would be very surprising to me. $\endgroup$ – Sasho Nikolov Oct 11 '12 at 20:42
  • 2
    $\begingroup$ (EXPTIME or EXP traditionally refers to 'the' complexity class $2^{O(p(n))}$, or more accurately the union of all such classes for polynomials $p(n)$; the class $2^{O(n)}$ is known by contrast simply as E, and it's not at all known to be a superset of NP; in fact, it's known not to be equivalent to NP - it's not complete under polynomial-time transformations - and there are oracles under which it's contained (and thus strictly contained) in NP. $\endgroup$ – Steven Stadnicki Oct 11 '12 at 23:49
8
$\begingroup$

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(2n), or in time 2O(n) for that matter. What is known is that all problems in NP can be solved deterministically in time 2poly(n) (= 2nO(1)). Time 2poly(n) is often called “exponential time” in complexity theory, but note that the same term “exponential time” can sometimes also refer to time 2O(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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.