**P (Polynomial time decidable problems)** is a class of problems which can be decided in polynomial time i.e., there’s an algorithm for such a problem which tells whether the solution of a given instance of a problem is true/false in O(n^k) time for some constant k.

For example, deciding whether there exists a path of at most k links between two vertices u and v is in P.

**NP (Non-deterministic polynomial time decidable problems)** is a class of problems which have short accepting certificates and efficient verification algorithms i.e., given a certificate of a solution, it is easy to check if the problem is satisfied.

Accepting certificate is information which can be used to decide if the answer is true or false.

Formally, a problem is in NP if there exists a verification algorithm A such that for any input x for which the answer is “true”, there is a certificate c such that |c| is polynomial and A(x,c) = true. For any x for which the answer is true, there is no certificate c such that |c| is polynomial and A(x,c) is true.

For example, given a graph G and a number k, deciding whether there exists a clique (complete subgraph) of size k, is in NP.

**P is a subset of NP** i.e., any problem that is in P is also in NP. It is easy to see that for any problem that can be decided in polynomial time, there exists a verification algorithm that given any certificate just ignores the certificate and returns the result of the polynomial-time algorithm.

**Whether NP is also a subset of P (i.e., P = NP) is an open question. No one knows yet.**

**NP-hard **is a class of problems which are hardest of all problems in NP. These are the problems such that if we can solve them fast, then we can solve all problems in NP fast and P would equal NP. NP-hard problems may be of any type: decision problems, search problems, or optimization problems so they may not even be in NP.

For example, the clique problem discussed above is NP-hard.

**NP-complete** is a class of problems which are in NP and are NP-hard. NP-complete problems transform to each-other by polynomial-time many-one reductions so if a polynomial-time algorithm exists for any one of them, then polynomial algorithms exist for all of them. However, no polynomial algorithm for any NP-complete problem has yet been found.

For example, the clique problem discussed above is NP-complete.

### Like this:

Like Loading...

*Related*