Thursday, September 26, 2013

P,NP,NP-complete,NP-Hard

P
A problem is said to have P complexoty if it can be solved by a deterministic turung machine(computer).
eg
Find if a graph can be coloured with two colors wothout any vertices being monochromaric.

NP
A problem is said to be NP if it can be solved in polynomial run time by Non deterministic Turing machine and the solution can be verified in polynomial run time by a deterministic Turing machine.
A non deterministic Turing machine is hypothetical computer with infinite parallel processing capability.

eg.
Verify is numbers x,y have an integer factor such that 1
NP-Complete

A problem is NP complete if it is NP and It can be reduced to another NP complete problem in polynomial run time by a deterministic Turing machine.
since all NP complete programs can be reduced to each other is there exists solution in polynomial run time for one NP complete problem then all NP complete problems have solution with polynomial run-time.
If any NP complete problem is solved in polynomial run time then P=NP
eg.
Binary Satisfactory problem(verify if there exists an interpretation which satisfies the given Boolean expression.)


NP-Hard
A problem is said to be NP hard if there exists an NP complete problem that can be reduced to the given problem.These problems are at least as hard as the hardest NP problem.NP hard problem need not be NP i.e they need not be solvable in polynomial run-time by Non deterministic Turing machine.
eg.
Travalling salesman problem.

P=NP
If an NP complete problem is proved to have solution in polynomial run time then all NP problems will have solution in polynomial run time.
If P=NP then there will be huge consequences particularly in cryptography since most of the modern algorithms are based on the assumption that the problem to find prime factors of a number is not solvable in polynomial run time.