P NP NP Complete

P NP NP Complete

Analysis of algorithm and computational complexity : P, NP, NP Complete

 

Algorithm :  A well defined computational procedure that takes some value / set of values as input , and produces some value / set of values as output.

 

Class P :  P is a class of language that are decidable in polynomial time on a deterministic single tape turing machine,

Example:   Kruskal's algorithm

                 Path problem  - in a graph to determine whether a directed path exist from s to t.

                 Relative prime [REL prime]

                 CFL   

Class NP : Polynomial time algorithm to solve them are not known to exist till now.

Example:  Hamiltonian path

                Composite problem (check for composite )

                Traveling salesman problem.

                CLIQUE problem

                The subset sum problem. 

 

NP Complete :If a polynomial time algorithm exist for an NP problem , then all problems in NP would be polynomial time solvable. These problems are called NP complete.

Example: Satisfiability Problem (SAT)
                SAT
               Vertex cover problem