deterministisch polynomielle Zeit
Einfache Sprache
$\mathrm{P}$ ist die Klasse von Sprachen, für die die Zugehörigkeit eines Wortes zu der Sprache “schnell” entscheiden werden kann.
Def. P
$\mathbf{P}$ ist die Klasse von Sprachen, die in polynomieller Laufzeit von einer DTM entscheidbar sind. Also
$$\mathbf{P} = \bigcup_k\mathbf{TIME}(n^k)\;,$$wobei $\mathbf{TIME}$ hier definiert ist.
Alternativ: Die Menge aller polynomiell entscheidbaren Sprachen bzw. Entscheidungsproblemen wird mit P bezeichnet:
$$P=\left\{L\subseteq\Sigma^*| \begin{aligned} &\text{es exisitert ein Algorithmus $A$, der $L$ in Laufzeit}\\&T_A(n)=\mathcal O(n^d) \text{ mit } d=\mathcal O(1) \text{ entscheidet} \end{aligned} \right\}$$
Eigenschaften
- $\mathbf{P}$ ist Invariant bzgl. des Computermodells. Also für alle Modelle die polynomial äquivalent zu der DTM sind.
- $\mathbf{P}$ ist die Klasse von Problemen die “realistisch” auf einem Computer lösbar sind.