This may serve as a cheat-sheet for someone who wants to get an understanding of the computational complexity terms, hopefully in the shortest possible time.

*P* – Problems that can be solved in polynomial time, obvious to this is, solutions to such problems can be verified in polynomial time as well. Example – Sorting problem.

*NP* (*Non-Deterministic Polynomial*) – Problems that can be verified in polynomial time but not necessarily can be solved in polynomial time. Example – Subset Sum Problem.

*NP Complete* – Problems that are as hard as any problem in *NP*. These are problems on the edge of NP space.

*NP Hard *– Problems that are higher in complexity than that of *NP Complete* problems. Example – Travelling Salesman Problem (TSP).

*EXP* – Problems that can be solved in exponential time. While TSP is a N! problem, it can be solved in exponential time using Dynamic Programming with 2^n*n^2.

*P!=NP* means, problems that can be verified in polynomial time can’t necessarily be solved in polynomial time.

### Like this:

Like Loading...

*Related*