NP-leicht

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
  1. siehe Polynomialzeithierarchie für die Notation
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.