What are P, NP, NP-complete, and NP-hard ?

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s