FP (Komplexitätsklasse)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 effektiv gelöst werden können.

Definition[Bearbeiten | Quelltext bearbeiten]

Eine linkstotale Relation ist in FP, falls ein deterministischer Algorithmus existiert, der zu einem gegebenen in polynomieller Zeit ein berechnet, so dass gilt.

Schränkt man zusätzlich auf rechtseindeutige Relationen und 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 in polynomialer Zeit deterministisch verifizieren lässt, ob gilt.

Weblinks[Bearbeiten | Quelltext bearbeiten]

FP. In: Complexity Zoo. (englisch)