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]
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.
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)
Vertex cover problem