FP (Komplexitätsklasse)

In der theoretischen Informatik, speziell der Komplexitätstheorie, beschreibt die Klasse FP die Menge aller Suchprobleme, die von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können (englisch function polynomial time, daher auch die Abkürzung). Vereinfacht ausgedrückt sind dies alle Suchprobleme, die auf einem klassischen Computer effizient gelöst werden können.

Definition

Eine linkstotale Relation $P\subseteq 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

• FP. In: Complexity Zoo. (englisch)