# 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.