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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.