Problem Detail: 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.
Asked By : avi
Answered By : Shaull
$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”.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9909
