This question already has an answer here:

Are all algorithms which have polynomial time complexity belong to P class ? And P class do not have any algorithm which does have not polynomial complexity ?

Are all algorithms which have non polynomial complexity belong to NP or NP-Hard or both ?

I am just trying to understand the basic relationship.


marked as duplicate by Juho, Pål GD, Nicholas Mancuso, Gilles Feb 19 '13 at 3:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from cstheory.stackexchange.com Feb 18 '13 at 22:04

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ Have a look at this question: cs.stackexchange.com/questions/9556/… $\endgroup$ – Paresh Feb 18 '13 at 22:20
  • 1
    $\begingroup$ I'm closing this question as a duplicate because I think Kaveh's great answer covers what you're asking. If there are things you don't understand in his answer, or if you think something isn't covered, edit your question to request clarifications and reply to this comment or flag to have your question reopened. $\endgroup$ – Gilles Feb 19 '13 at 3:39

$P$ is defined as the class of (decision) problems that have an algorithm that solves them in polynomial time (in a TM, or a polynomially-equivalent model). Thus, $P$ contains exactly these problems, no more and no less.

As for $NP$- the situation is more delicate. A problem is in $NP$ if it has a nondeterministic algorithm that runs in polynomial time. An equivalent, more user-friendly definition, is that given a solution to the problem, you can verify it's correctness in time polynomial in the size of the problem. For example, given a graph and a path that claims to be a Hamiltonian, you can verify in polynomial time that it is indeed a Hamiltonian path. Thus, the problem of deciding if a graph has a Hamiltonian path is in $NP$.

Clarification: $NP$ is a class of problems, not of algorithms. An algorithm doesn't belong to $NP$.

Now, some problems are known not to have a polynomial time algorithm. This doesn't mean that they are in $NP$. In fact, some problems are known not to be in $NP$. For example, any $NEXP$-hard problem.

Regarding $NP$-hard problems - since we don't know whether $P=NP$ or not, we don't know if every problem outside $P$ is $NP$-hard. If $NP=P$, then every problem is $NP$-hard (except $\Sigma^*$ and $\emptyset$).

This answer (which is by far incomplete) covers about 3 weeks of material in a basic complexity course. Perhaps consider thoroughly reading a textbook, such as Sipser's "Theory of Computation".

  • $\begingroup$ You can add that $P\subset NP$ to make clear that $P$ and $NP$ are not disjoint. $\endgroup$ – saadtaame Feb 19 '13 at 1:03
  • $\begingroup$ If you think you can add something to the existing answers (e.g. a new perspective), you might want to add your answer here. $\endgroup$ – Raphael Feb 19 '13 at 6:01

All algorithms that solve some decision problem in polynomial time show that their problems are in $P$. But there are certainly algorithms that don't take polynomial time for problems in $P$. You could sort by generating all $n!$ permutations of the input, and check each if it is sorted. That algorithm does take a more than exponential time, but the problem has a solution in polynomial time.


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