NP
Set
| definiendum | $ L\in \mathrm{\bf{NP}} $ |
| inclusion | $ L\subseteq\{0,1\}^* $ |
| range | $ M $ … polynomial time 2-tape Turing machine |
| range | $ p:\mathbb{N}\to\mathbb{N} $ … polynomial |
| range | $ x,u\in\{0,1\}^* $ … bit string |
| postulate | $\exists M,p.\ \forall x.\ x\in L\Leftrightarrow \exists u.\ \left(M(x,u) = 1\land \left|u\right|=p(\left|x\right|)\right) $ |
Discussion
todo: Requirements Polynomial time Turing machine
The definition says that a language $L$ is in ${\bf{NP}}$ under the following condition: You don't necessarily have to be able to decide $x\in L$ via a real algorithm, but at least you must be able to confirm $x\in L$ would you have a post-Turing machine, which for every individual $x$, is allowed to cleverly adopt the behavior of it's transition function via input $u$ from an extra tape. The additional input, called certificate, is allowed to depend on each individual $x$, although is has to be at worst polynomially longer (otherwise the machine couldn't even read the second tape in reasonable time).
The machine $M$ still depends on the input $x$ in a computational manner, because for $x\notin L$ it is not allowed for there to be any misleading certificate resulting in the $M(x,u) = 1$. In fact, for $x\notin L$ the machine doesn't tell you anything (the class is defined by that predicate is called ${\bf{NP}}$). If $u$ also knew if $x\notin L$, then it could just be a yes/no answer and any language could be decided this way. Instead, the above definition permits the interpretation $M$ to be the verifier.
Examples
A problem in $\mathrm{\bf{NP}}$ is the Boolean satisfiability problem. Finding out if a circuit, given via $x$, can be satisfied is hard. But as $u$ is allowed to be a string among the right inputs, having $M$ be the machine which tests $u$ on a given circuit which returns a positive answer if it works directly answers the initial question.
Theorem
In any case, it turns out that there are no languages which are decidable using a certificate but not by a normal Turing machine. However it seems that the magical machine would at least allow one to calculate problems in polynomial time, which aren't in ${\bf{P}}$. Or is ${\bf{P}}={\bf{NP}}$?
The set ${\bf{NP}}$ can also be defined by introducing the non-deterministic Turing machine (NDTM) which is the post-Turing machine trying several computations at once. Formally it's a machine with two transition functions $\delta_0,\delta_1$ and at any time step the configuration is doubled and both possibilities are considered. Hence computation branches exponentially in time and the machine terminates as soon as any branch returns a result.
We define $\mathrm{\bf{NP}}$ (?? is this right?) exactly like $\mathrm{\bf{NTIME}}$, only with $NDTM$'s instead of $TM$'s. Then
$ \mathrm{\bf{NP}} = \bigcup_{k\in\mathbb{N}} \mathrm{\bf{NTIME}}(n^k) $
Requirements
Subset of
