3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Have a look at this question: cs.stackexchange.com/questions/9556/… $\endgroup$
    – Paresh
    Commented Feb 18, 2013 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$ Commented Feb 19, 2013 at 3:39

2 Answers 2

2
$\begingroup$

$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".

$\endgroup$
2
  • $\begingroup$ You can add that $P\subset NP$ to make clear that $P$ and $NP$ are not disjoint. $\endgroup$
    – mrk
    Commented Feb 19, 2013 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
    Commented Feb 19, 2013 at 6:01
1
$\begingroup$

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.

$\endgroup$

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