Skip to content

Instantly share code, notes, and snippets.

@alyssaq

alyssaq/NP-complexity-algorithm.md

Last active December 21, 2015 15:29
Show Gist options
  • Save alyssaq/6326965 to your computer and use it in GitHub Desktop.
Save alyssaq/6326965 to your computer and use it in GitHub Desktop.
Download ZIP
NP (complexity)
Raw
NP-complexity-algorithm.md

Definitions

NP = Non-deterministic Polynomial time.
It is the set of all decision problems for which the answer 'yes' have verifiable proofs to prove that the answer is indeed 'yes'.
Non-deterministic = different behaviours on different algorithm run. E.g. Merge sort
Polynomial time = algo has an upper-bound run-time by a polynomical expression in the size of its inputs. E.g. O(n log n)

Complexity classes of decision problems (yes-or-no)

P: Solvable in deterministic Turing machine in polynomial time
NP: Solvable in non-deterministic Turing machine in polynomial time
ZPP: Solvable in with zero error on a probabilistic Turing machine in polynomial time
RP: Solvable in with 1-sided error on a probabilistic Turing machine in polynomial time
BPP: Solvable in with 2-sided error on a probabilistic Turing machine in polynomial time
BQP: Solvable in with 2-sided error on a quantum Turing machine in polynomial time

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment