deterministisch polynomielle Zeit mit Orakel-TM

Einfache Sprache

Def. deterministisch polynomielle Zeit mit Orakel-TM

Deterministisch polynomielle Zeit mit Orakel-TM oder auch $\mathbf{P}^A$ ist die Klasse an Sprachen die in polynomieller Laufzeit von einer Orakel-Turingmaschine, mit einem Orakel für die Sprache $A$, entschieden werden.