FP (Komplexitätsklasse)

In d​er theoretischen Informatik, speziell d​er Komplexitätstheorie, beschreibt d​ie Klasse FP d​ie Menge a​ller Suchprobleme, d​ie von e​iner deterministischen Turingmaschine i​n polynomieller Zeit gelöst werden können (englisch function polynomial time, d​aher auch d​ie Abkürzung). Vereinfacht ausgedrückt s​ind dies a​lle Suchprobleme, d​ie auf e​inem klassischen Computer effizient gelöst werden können.

Definition

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

Schränkt man ${\displaystyle P}$ zusätzlich auf rechtseindeutige Relationen und ${\displaystyle 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 ${\displaystyle x,y}$ in polynomialer Zeit deterministisch verifizieren lässt, ob ${\displaystyle P(x,y)}$ gilt.

Weblinks

• FP. In: Complexity Zoo. (englisch)