FP (Komplexitätsklasse)

In der theoretischen Informatik, speziell der Komplexitätstheorie, beschreibt die Klasse FP (Abkürzung aus dem Englischen: Function Polynomial-Time) die Menge aller Suchprobleme, die von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können. Vereinfacht ausgedrückt sind dies alle Suchprobleme, die auf einem klassischen Computer effektiv gelöst werden können.

Definition

Eine linkstotale Relation $P \sube X \times Y$ ist in FP, falls ein deterministischer Algorithmus existiert, der zu einem gegebenen $x$ in polynomieller Zeit ein $y$ berechnet, so dass $P(x, y)$ gilt.

Schränkt man $P$ zusätzlich auf rechtseindeutige Relationen und $Y$ auf Wahrheitswerte ein, erhält man genau die Komplexitätsklasse P.

Analog zur Klasse NP kann eine allgemeinere Klasse FNP definieren. Für Elemente in dieser Klasse wird nur gefordert, dass sich für ein gegebenes Wertepaar $x,y$ in polynomialer Zeit deterministisch verifizieren lässt, ob $P(x,y)$ gilt.

Weblinks

• Eintrag im Complexity Zoo