The exact relation between complexity classes and algorithm complexities [duplicate]

Question

This question already has an answer here:

• What is the definition of P, NP, NP-complete and NP-hard? 7 answers

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.

Answer 1

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

Answer 2

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.