P - NP

Definitions

P
NP
Polynomial Time Redcutions
NP-Hard
NPC
Pseudo Polynomial Time Algorithms
Strongly NP-Complete problems
Approximation Algorithms
PTAS (Polynomial Time Approximation Scheme)
FPTAS (Fully Polynomial Time Approximation Scheme)

Suggestions and Errors, please mail: purukulk@cs.umass.edu

UNDER CONSTRUCTION

P : A decision problem Ø is said to be in the set P if and only if there exists a polynomial time algorithm A such that, X is a "Yes" instance of Ø if and only if A(X) = "Yes".

NP : A decision problem Ø is in NP if and only if there exists a polynomial time algorithm A such that, X is a "Yes" instance of Ø if and only if there exists some Y (Y is polynomial in the size of the input X, |Y| = O(|X|^k)) and A(X,Y) = "Yes".
Y is said to be a witness or certificate that can be verified in polynmial time that A(X) = "Yes". NP is said to be a class of intractable problems since we cannot find the certificate Y efficiently (in polynomial time).

Polynomial-time reductions : Ø₂ is polynomial time reducible to Ø₁, (Ø₂ <= _p Ø₁), if and only if there exits a polynomial- time algorithm f that transforms any input instance x of Ø₂ to an instance f(x) of Ø₁ such that,
x is a "Yes" instance of Ø₂ iff f(x) is a "Yes" instance of Ø ₁
x is a "No" instance of Ø₂ iff f(x) is a "No" instance of Ø ₁

. inputs of Ø₂ inputs of Ø₁

          ------------               -----------
          |          |               |         |
          |   YES  -------------------> YES    |
          |          |               |         |
          |~~~~~~~~~~|      f        |~~~~~~~~~|
          |          |               |         |
          |   NO   ------------------->  NO    |
          |          |               |         |
          ------------               -----------
	  f: polynomial-time reduction function

If for decision problems A and B, A <=_pB,
if B in P then A in P
if A in NP then B in NP
if B not in P, cannot say anything about A

		     A
                     ---------------------------------
                     |                               |
                     |                               |
               x     |    -------       -------      |
             ------> |    |  f  |  f(x) |  B  | -----|------> Yes / No
                     |    |     | ----->|     |      |
                     |    -------       -------      |
                     |                               |
                     |                               |
                     ---------------------------------

x is any input instance of problem A.
f is a polynomial time function that tranforms input x to f(x).
f(x) is the input instance of another problem B. Problem B can be solved in polynomial time.
Since B can be sovled in polynomial time and f is a polynomial time reduction function, problem A can be solved in polynomial time by converting the input instance x to f(x) and using it as input to problem B. Correctness of the output follows from the definition of polynomial-time reduction function. Thus problem A can be solved in polynomial time.
Note: if A belongs to NP, then problem B also has to be in NP, else using the above reduction we can solve A in polynomial time.

NP-Hard : A decision problem Ø is NP-Hard if and only if, for all Ø' in NP, Ø' <=_p Ø.

NPC (NP-Complete) : A decision problem Ø is NP-Complete(NPC), if and only if Ø is in NP and Ø is in NP-Hard.
Note: if Ø in NPC and Ø in P, then P = NP !

Relationships amongst P, NP, NPC and NP-Hard

         ____________________________ 
         |                          |
         |           NP             |
         |                          |
         |  ______       ___________|___________
         |  |    |       | NP-Hard  ~          |  
         |  | P  |       |    &     ~  NP-Hard | 
         |  |    |       |  NPC     ~          | 
         |  ------       -----------------------
         |                          |
         ----------------------------

Pseudo-Polynomial Algorithms :

Strong NP-Complete Problems :

Apprximation Algorithms :

Polynomial Time Approximation Scheme :

Fully Polynomial Time Approxmation Scheme :

Suggestions and Errors, please mail: purukulk@cs.umass.edu

Home

UNDER CONSTRUCTION