imported>Gak69: Reference-Tag eingefügt

2023-08-07T04:28:07Z

Reference-Tag eingefügt

Neue Seite

{{Belege fehlen}}
In der [[Komplexitätstheorie]] bezeichnet die Komplexitätsklasse '''NP-leicht''' (auch FP<sup>NP</sup><ref>siehe [[Polynomialzeithierarchie#Definition mit Orakel-Turingmaschinen|Polynomialzeithierarchie]] für die Notation</ref>, wobei FP für funktionale [[Polynomialzeit]] steht) die Menge aller Funktionen, die in [[Polynomialzeit|polynomieller Zeit]] durch eine [[Determinismus (Algorithmus)|deterministische]] [[Turingmaschine]] mit Hilfe einer [[Orakel-Turingmaschine]] für ein [[Entscheidbar|Entscheidungsproblem]] aus der [[Komplexitätsklasse NP|Klasse NP]] berechnet werden können.

== Einzelnachweise ==
<references />

[[Kategorie:Komplexitätstheorie|Npleicht]]

NP-leicht - Versionsgeschichte

imported>Gak69: Reference-Tag eingefügt