Computational Complexity Terminology

* Deterministic:
permitting at most one next move at any step in a computation.

* Nondeterministic:
permitting more than one choices of next move at ‘some’ step in a computation.

* Turing Machine:
a model of computation consisting of a finite state machine controller, a read-write head, and an unbounded sequential tape. Depending on the current state and symbol read on the tape, the machine can change its state and move the head to the left or right. Unless otherwise specified, a Turing machine is ‘deterministic’.

* P:
a complexity class of languages that can be accepted by a deterministic Turing machine in polynomial time.

* NP:
the complexity class of ‘decision problems’ for which answers can be checked by an algorithm whose run time is polynomial in the size of the input. Note that this doesn’t require or imply that an answer can be found quickly, only that any Claimed Solution can be VERIFIED quickly. “NP” is the class that a ‘Nondeterministic Turing machine’ accpets in Polynomial time.

* NP-complete:
the complexity class of ‘decision problems’ for which answers can be checked for correctness, given a ‘certificate’, by an algorithm whose run time is polynomial in the size of the input (that is, it is ‘NP’) and no other NP problem is more than a polynomial factor harder. Informally, a problem is NP-complete if answers can be verified quickly, and a quick algorithm to solve this problem can be used to solve all other NP problems quickly.

* NP-hard:
the complexity class of ‘decision problems’ that are intrinsically harder than those that can be solved by a nondeterministic Turing machine in polynomial time. When a decision version of a combinatorial ‘optimization problem’ is proved to belong to the class of NP-complete problems, then the optimization version is NP-hard.