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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} berechnet, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(x, y)} gilt.

Schränkt man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x,y} in polynomialer Zeit deterministisch verifizieren lässt, ob Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(x,y)} gilt.

Weblinks

• FP. In: Complexity Zoo. (englisch)