nichtdeterministisch polynomielle Zeit mit Orakel-TM

Einfache Sprache

Def. nichtdeterministisch polynomielle Zeit mit Orakel-TM

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