NP-leicht

In der Komplexitätstheorie bezeichnet die Komplexitätsklasse NP-leicht (auch FP^NP, 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.