# P != NP

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.