P (Polynomial-time)

Set of decisional problems that can be resolved in polynomial time.

NP (Non-deterministic Polynomial-time)

Set of decisional problems that can be verified in polynomial time.

Lemma :   P ⊆ NP

A problem ( in P ) that can be resolved in polynomial time with an algorithm, can also be verified in polynomial time by the same ( therefore it is in NP ).

note:   P ⊆ NP   reads as : " P is a subset of NP " and it means that either P = NP or P ⊂ NP.

P versus NP problem

It is an unresolved problem with a prize of 1'000'000 $ the proof that either:

• P = NP The set P is equal to the set NP.

• P ⊂ NP The set P is a proper subset of the set NP.
  ( which implies that P ≠ NP ).

NP-complete

Set of decisional problems. Proper subset of NP ( can always be verified in polynomial time ).

 NP-complete ⊂ NP

Has the following characteristics:

• Every problem in NP can be reduced in polynomial time to a problem in NP-Complete.
• If an algorithm capable of solving any NP-complete problem were found then such an algorithm would be capable of solving any problem in NP. Such an algorithm has not yet been found.

Example of NP-complete problem: SAT

NP-hard

Set of problems not limited to decisional problems; at least as hard as the problems in NP-complete.

NP-hard is a proper superset of NP-complete. ( may or may not be verifiable in polynomial time ).

 NP-complete ⊂ NP-hard

Has the following characteristics:

• Every problem in NP-complete can be reduced in polynomial time to a problem in NP-Hard.
• If an algorithm capable of solving any NP-hard problem were found then such an algorithm would be capable of solving any problem in NP. Such an algorithm has not yet been found.

Example of NP-hard problem: SAT ( since NP-Complete ⊂ NP-Hard )
Example of NP-Hard but not NP-Complete problem: Halting Problem