nichtdeterministisch polynomielle Zeit
Einfache Sprache
Die Klasse $\mathbf{NP}$ ist genau die Menge aller Sprachen, die durch einen nichtdeterministischen Algorithmus in Polynomialzeit entschieden werden können.
$\mathbf{NP}$ ist die Klasse von Sprachen, für die die Zugehörigkeit eines Wortes zu der Sprache “schnell” verifiziert werden kann.
Definition über Verifizierer
Def. NP
Die Klasse aller polynomiell verifizierbar Sprachen. Also
$$\mathbf{NP}=\left\{L\subseteq\Sigma^*| \text{es exisitert ein }\textit{polynomieller Verifizierer}\text{ für }L \right\}$$
Alternative Definitionen
Def. NP
Mit NTIME ergibt sich folgende Definition:
$$\mathbf{NP}=\bigcup_k\mathbf{NTIME}(n^k)$$