Recent Post

Complexity Classes: P, NP, NPH and NPC

COMPLEXITY THEORY

  Computational theory is mainly used to recognize whether the problem that is decidable is easy or hard. This can be calculated by means of time complexity and space complexity.

Complexity Classes
 P-space Problem
          The language in P-space represents the polynomial space complexity of the language.

 NP-space Problem 
          The language in NP space represents the non polynomial space complexity of the language.

P-problem

          P is the class of problems that can be solved by deterministic algorithms in a time that is polynomially related to the size of the respective problem instance.
  It consists of all language accepted by some deterministic turing machine that runs in polynomial amount of time, as a function of input length.

Example:-
 1-SAT
 2-SAT
 Unary partition
 Shortest path
 2-colourability
 Eular cycle
 Equivalence of DFA
 Min cut
 Shortest cycle in a graph
 Sorting

NP-problem
    NP is the class of problems that can be solved by nondeterministic algorithms in a time that is polynomially related to the size of the respective problem instance.
           It consists of all languages that are accepted by non deterministic turing machines with a polynomial bound on the time taken along any sequence of non deterministic choices.
     Example:-
         1. Traveling sales person problem and
         2. Sub graph isomorphism. 



NP-Hard Problem
   If there is a language ⛌ such that every language Y in NP can be polynomially reducible to ⛌ and we cannot prove that ⛌ is in NP then ⛌ is said to be NP-Hard problem.
                  A problem ⛌ is NPH iff  ∀ Y ∈ NP , Y ≤p ⛌.
    Example:- Turing machine halting problem.

NP-Complete Problem
       If there is a language ⛌ such that every language Y in NP can be polynomially reducible to ⛌ and ⛌ is in NP then ⛌ is said to be NP-Hard problem.If NP hard problem is present in NP then it is called NP-complete problem.
        A problem ⛌ is NPC iff ∀ Y ∈ NP, Y ≤p ⛌ ⛌∈ NP
  
Example:-
 3-SAT
 Traveling sales man problem
 Hamilton circuit problem
 Vertex cover problem
 Independent set problem
 Chromatic number problem
 Coloring problem
 Sub-graph isomorphism problem
 Edge cove problem
 Knapsack problem
 Max cut

REDUCTION

   P1 ≤ P2: Problem P1 is reducible to a problem P2. It means problem P2 is at-least as hard as problem P1.
   If P1 ≤ P2 and P1 is undecidable then P2 is also undecidable.
   If P1  ≤ P2 and P2 is decidable then P1 is also decidable.
   If P1  ≤ P2  and P2 is recursive then P1 is also recursive.
   If P1  ≤ P2 and P2 is recursive enumerable then P1 is also recursive enumerable.
   If P1  ≤ P2 and P2 is P-problem then P1 is also P-problem.
   If P1  ≤ P2 and P2 is NP-problem then P1 is also NP-problem.
   If NP-complete is in P then P=NP.
 

No comments