NP-leicht

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

In der Komplexitätstheorie bezeichnet die Komplexitätsklasse NP-leicht (auch FPNP[1], 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

[Bearbeiten | Quelltext bearbeiten]
  1. ↑ siehe Polynomialzeithierarchie für die Notation
Abgerufen von „https://de.wikipedia.org/w/index.php?title=NP-leicht&oldid=236188442“