complexity level problem
P
Such like Negtive weight cycle detection problem.
Exists a polynomial algorithm to solve this problem.
is set of problems that can be solved by a deterministic Turing machine in Polynomial time.
NP
Such as Tetrics problem.
Exists a polynomial algorithm to verify this problem.
is set of decision problems that can be solved by a Non-deterministic Turing Machine in Polynomial time.
Informally, NP is set of decision problems which can be solved by a polynomial time via a “Lucky Algorithm”, a magical algorithm that always makes a right guess among the given set of choices.
Hence NP is the super set of P.
NP-Complete
Such like SAT, Mine sweep, Sudoku, Travel sales path problem.
- Is an NP problem.
- any NP problem could be reduced to this problem.
NP-hard
Such as Tetrics problem.
- any NP problem could be reduced to this problem.
Hence NP-Hard is the super set of NP-Complete.
EXP
Such as Chess problem.
Means could solve a problem in exponetial time.
Apparantly EXP is the super set of NP.
R
The problem is recursive problem, which means it could be solved in finite time.
But unfortunately most of problems are not in R, for example halting problem is not in R.
Apparantly R is the super set of EXP.