NP-leicht

Vorlage:Hinweisbaustein In der Komplexitätstheorie bezeichnet die Komplexitätsklasse NP-leicht (auch FP^NP<ref>siehe Polynomialzeithierarchie für die Notation</ref>, wobei FP für funktionale Polynomialzeit steht) die Menge aller Funktionen, die in polynomieller Zeit durch eine deterministische Turingmaschine mit Hilfe einer Orakel-Turingmaschine für ein Entscheidungsproblem aus der Klasse NP berechnet werden können.

Einzelnachweise

<references />