HomeWissen Stichwortverzeichnis Tags

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

Probleme in $\mathbf{P}$

Home: