**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**

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.