Was genau sind die Klassen FP, FNP und TFNP?

In seinem Buch Computational Complexity definiert Papadimitriou FNP wie folgt:

Angenommen, $L$ ist eine Sprache in NP . Nach Satz 9.1 gibt es eine polynomisch-zeitlich entscheidbare, polynomisch ausgeglichene Beziehung $R_L$ so dass für alle Zeichenketten $x$ : Es gibt eine Zeichenkette $y$ mit $R_L(x,y)$ genau dann, wenn $x\in L$ . Das mit verbundene Funktionsproblem $L$, das mit $FL$ , ist das folgende Rechenproblem:

Wenn $x$ , finde eine Zeichenkette $y$ so dass $R_L(x,y)$ wenn eine solche Zeichenkette existiert; Wenn keine solche Zeichenfolge vorhanden ist, geben Sie "no" zurück.

Die Klasse aller Funktionsprobleme, die wie oben mit der Sprache in NP verbunden sind, heißt FNP . FP ist die Unterklasse, die sich ergibt, wenn wir nur Funktionsprobleme in FNP betrachten , die in Polynomzeit gelöst werden können.

(...)

(...) nennen wir ein Problem $R$ in FNP total, wenn es für jeden String $x$ mindestens ein $y$ so dass $R(x,y)$ . Die Unterklasse von FNP, die alle Gesamtfunktionsprobleme enthält, wird als TFNP bezeichnet .

In einem Venn-Diagramm in der Kapitelübersicht impliziert Papadimitriou, dass FP $\subseteq$ TFNP $\subseteq$ FNP .

Ich habe eine harte Zeit zu verstehen , warum genau gilt, dass FP $\subseteq$ TFNP da Probleme in FP müssen nicht per se insgesamt sein.

Zum besseren Verständnis habe ich in der Literatur nach einer wasserdichten Definition von FP , FNP und Sorten gesucht, ohne Erfolg.

Meiner (bescheidenen) Meinung nach gibt es zu diesen Themen wenig (korrektes!) Didaktisches Material.

Bei Entscheidungsproblemen sind die Klassen Sätze von Sprachen (dh Sätze von Zeichenfolgen).

Was genau sind die Klassen für Funktionsprobleme? Sind sie Zusammenhänge, Sprachen, ...? Was ist eine feste Definition?

Emil Jerabeks Kommentar ist eine schöne Zusammenfassung, aber ich wollte darauf hinweisen, dass es andere Klassen mit klareren Definitionen gibt, die mehr oder weniger dasselbe Konzept erfassen und die Beziehung zwischen all diesen Dingen klarstellen.

[Warnung: Während ich glaube, dass ich die Definitionen richtig verstanden habe, spiegeln einige der folgenden Dinge meine persönlichen Vorlieben wider - ich habe versucht, klar zu machen, wo das war.]

In der deterministischen Welt, ist eine Funktionsklasse nur eine Sammlung von Funktionen (in dem üblichen mathematischen Sinne des Wortes „Funktion“, das heißt, eine Karte ). Gelegentlich möchten wir "Teilfunktionen" zulassen, deren Ausgabe für bestimmte Eingaben "undefiniert" ist. (Gleichwertig Funktionen , die auf einer Untergruppe von definierten Σ * und nicht alle davon.)$\Sigma^* \to \Sigma^*$$\Sigma^*$

Leider gibt es zwei verschiedene Definitionen für , und soweit ich das beurteilen kann, sind sie nicht äquivalent (obwohl sie "moralisch" äquivalent sind).$\mathsf{FP}$

• (Definition 1) ist die Klasse von Funktionen, die in Polynomzeit berechnet werden können. Wann immer Sie F P sehen und es ist nicht in einem Kontext, in dem von F N P , T F N P gesprochen wird , ist dies die Definition, die ich annehme.$\mathsf{FP}$$\mathsf{FP}$$\mathsf{FNP}, \mathsf{TFNP}$

In der nichtdeterministischen Welt wird es ein bisschen komisch. Dort ist es zweckmäßig, "teilweise mehrwertige Funktionen" zuzulassen. Es wäre natürlich auch so etwas eine nennen binäre Relation , die eine Teilmenge von ist . Unter dem Gesichtspunkt der Komplexität ist es jedoch oft philosophisch und mental nützlich, diese Dinge als "nicht deterministische Funktionen" zu betrachten. Ich denke, viele dieser Definitionen werden durch die folgenden Klassen geklärt (deren Definitionen vollständig standardisiert sind, wenn auch nicht sehr bekannt):$\Sigma^* \times \Sigma^*$

• : Die Klasse von "partiellen mehrwertigen Funktionen", die von einer nicht deterministischen Maschine in der Polynomzeit berechnet werden können. Dies bedeutet, dass es eine nicht deterministische Mehrfachzeitmaschine gibt und dass sie bei Eingabe x in jedem nicht deterministischen Zweig wählen kann, eine Ausgabe zu akzeptieren und durchzuführen oder eine Ausgabe abzulehnen und keine Ausgabe vorzunehmen. Der "mehrwertige" Ausgang am Eingang x ist dann die Menge aller Ausgänge an allen nicht deterministischen Zweigen, wenn x als Eingang angegeben wird. Beachten Sie, dass dieser Satz leer sein kann, sodass dies als "mehrwertige Funktion" nur teilweise sein kann. Wenn wir es in binären Beziehungen sehen, entspricht dies der Beziehung { ( x , y ) : $\mathsf{NPMV}$$x$$x$$x$ausgegeben  .$\{(x,y) : y \text{ is output by some branch of the computation on input } x\}$

• : Summe der "Funktionen" in N P M V , dh an jedem Eingangxakzeptiert mindestens ein Zweig (und gibt daher per Definition einen Ausgang aus)$\mathsf{NPMV}_t$$\mathsf{NPMV}$$x$

• : einwertig (möglicherweise teilweise) Funktionen in N P M V . Hier besteht jedoch eine gewisse Flexibilität dahingehend, dass möglicherweise mehrere Zweige akzeptieren. Wenn jedoch ein Zweig akzeptiert wird, muss sichergestellt sein, dass alle akzeptierenden ZweigedieselbeAusgabe liefern (sodass sie wirklich einwertig sind). Allerdings ist es immer noch möglichdass kein Zweig akzeptiert, so dass die Funktion nur eine „Teilfunktion“ (dh nicht definiert auf alle Σ * ).$\mathsf{NPSV}$$\mathsf{NPMV}$$\Sigma^*$

• : einwertig Gesamt Funktionen in N P S V . Diese wirklich sind Funktionen, im üblichen Sinne des Wortes, Σ * → Σ * . Es ist keine allzu schwere Übung zu sehen, dass N P S V t = F P N P ∩ c o N P (unter Verwendung von Def 1 für FP oben).$\mathsf{NPSV}_t$$\mathsf{NPSV}$$\Sigma^* \to \Sigma^*$$\mathsf{NPSV}_t = \mathsf{FP}^{\mathsf{NP} \cap \mathsf{coNP}}$

Wenn wir von potentiell mehrwertigen Funktionen sprechen, ist es nicht mehr wirklich sinnvoll, von der Eindämmung von Komplexitätsklassen zu sprechen: bedingungslos, weil N P S V keine mehrwertigen "Funktionen enthält “, aber N P M V der Fall ist. Stattdessen sprechen wir von "c-Containment", bezeichnet mit ⊆ c . Eine (potentiell partielle, mehrwertige) Funktion f verfeinert eine (potentiell partielle, mehrwertige) Funktion g, wenn: (1) für jeden Eingang x, für den $\mathsf{NPMV} \not\subseteq \mathsf{NPSV}$$\mathsf{NPSV}$$\mathsf{NPMV}$$\subseteq_c$$f$$g$$x$$g$macht eine Ausgabe, , und (2) die Ausgaben von f sind immer eine Teilmenge der Ausgaben von g . Die richtige Frage ist dann, ob jede N P M V -Funktion eine N P S V -Verfeinerung aufweist. Wenn ja, schreiben wir N P M V ⊆ c N P S V .$f$$f$$g$$\mathsf{NPMV}$$\mathsf{NPSV}$$\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$

• (etwas weniger Standard) ist die Klasse der (potentiell partiellen) Funktionen, die in Polyzeit berechenbar sind. Das heißt, eine Funktion f : D → & Sigma; * ( D ⊆ & Sigma; * ) ist in P F , wenn es eine Poly-time deterministische Maschine so istdaß, anEingängen x ∈ D die Maschinenausgänge f ( x ) , und anEingängen x ∉ D Die Maschine gibt nichts aus (/ lehnt ab / sagt "nein" / wie auch immer Sie es ausdrücken möchten).$\mathsf{PF}$$f\colon D \to \Sigma^*$$D \subseteq \Sigma^*$$\mathsf{PF}$$x \in D$$f(x)$$x \notin D$

• ist eine Klasse von "Funktionsproblemen" (und keine Klasse von Funktionen). Ich würde auch anrufen F N P eine „Beziehungsklasse“, aber wirklichwas WorteSie es beschreiben Sie brauchensich danach zu klären, weshalb ich auf diese Definition nicht besonders teilweise bin. Für jede binäre Relation R ⊆ Σ * × Σ * gibt es ein zugehöriges "-Funktion Problem"Was ist ein Funktionsproblem? Ich habe keine klare mathematische Definition, wie ich es für Sprache / Funktion / Beziehung tue. Vielmehr wird definiert, was eine gültige Lösung ist:$\mathsf{FNP}$$\mathsf{FNP}$$R \subseteq \Sigma^* \times \Sigma^*$$R$$f$so dass , wenn dann f Ausgänge jeder derartiger y , und sonst f machen keinen Ausgang. F N P ist die Klasse von Funktionsproblemen, die mit Beziehungen R verbunden sind, so dass R ∈ P (wenn es als eine Sprache von Paaren betrachtet wird) und p-ausgeglichen ist. So F N P ist nicht eine Klasse von Funktionen, noch eine Klasse von Sprachen, sondern eine Klasse von „Funktionsstörungen“ , wo „Problem“ hier definiert ist grob in Hinblick darauf, was es bedeutet , es zu lösen.$(\exists y)[R(x,y)]$$f$$y$$f$$\mathsf{FNP}$$R$$R \in \mathsf{P}$$\mathsf{FNP}$

• ist dann die Klasse von Funktionsproblemen in F N P - definiert durch eine Beziehung R wie oben - ein solches R ist insgesamt in dem Sinne, dass für jedes x ein y existiert,so dass R ( x , y ) .$\mathsf{TFNP}$$\mathsf{FNP}$$R$$R$$x$$y$$R(x,y)$

Um nicht schreiben zu müssen wie "Wenn jedes Funktionsproblem (bzw. T F N P ) eine Lösung in P F (bzw. F P gemäß obiger Definition) hat, dann ..." in In diesem Zusammenhang wird Definition 2 von F P verwendet , die lautet:$\mathsf{FNP}$$\mathsf{TFNP}$$\mathsf{PF}$$\mathsf{FP}$$\mathsf{FP}$

• (Definition 2) ist die Klasse von Funktionsproblemen in F N P , die eine Mehrfachzeitlösung haben. Man kann annehmen, dass die Lösung (= Funktion) hier total ist, indem man eine spezielle Zeichenkette y 0 auswählt, die kein gültiges y für ein beliebiges x ist , und die Funktion y 0 ausgibt,wenn es sonst kein gültiges y geben würde . (Falls erforderlich, können wir die Beziehung R ändern,indem wir jedem y eine 1voranstellenund dann y 0 als Zeichenfolge 0annehmen. Dies ändert nichts an der Komplexität der beteiligtenElemente.)$\mathsf{FP}$$\mathsf{FNP}$$y_0$$y$$x$$y_0$$y$$R$$y$$y_0$

Hier ist, wie diese verschiedenen Definitionen zueinander in Beziehung stehen: (Definition 2, was Sie annehmen sollten, weil es sich in einem Kontext befindet, in dem es mit F N P verglichen wird ) ist äquivalent zu N P M V ⊆ c P F . T F N P ≤ F P (def 2) ist äquivalent zu N P M V t ≤ c F P (def 1).$\mathsf{FNP} \subseteq \mathsf{FP}$$\mathsf{FNP}$$\mathsf{NPMV} \subseteq_c \mathsf{PF}$$\mathsf{TFNP} \subseteq \mathsf{FP}$$\mathsf{NPMV}_t \subseteq_c \mathsf{FP}$

Zusätzlich zu Joshuas ausführlicher Antwort möchte ich die folgenden Definitionen aus Elaine Ruchs Automaten, Rechenfähigkeit und Komplexität hinzufügen .

Die Klasse FP : Eine binäre Beziehung ist in F P, wenn es einen deterministischen Polynomzeitalgorithmus gibt, der bei einer beliebigen Eingabe x ein y finden kann, so dass ( x , y ) ∈ Q ist .$Q$$\mathsf{FP}$$x$$y$$(x,y) \in Q$

Die FNP Klasse : Eine binäre Beziehung in ist F N P iff es eine deterministische Polynomzeit ist, Verifizierer eines willkürliches Eingangspaar gegeben ( x , y ) , bestimmt , ob ( x , y ) ∈ Q . Entsprechend ist Q in F N P, wenn es einen nichtdeterministischen polynomiellen Zeitalgorithmus gibt, der bei einer beliebigen Eingabe x ein y finden kann, so dass ( x , y ) ∈ $Q$$\mathsf{FNP}$$(x,y)$$(x,y) \in Q$$Q$$\mathsf{FNP}$$x$$y$$(x,y) \in Q$

Aus diesen Definitionen ist es , dass klar . Sie hat auch kurz spricht über Probleme außerhalb von F N P .$\mathsf{FP} \subseteq \mathsf{TFNP} \subseteq \mathsf{FNP}$$\mathsf{FNP}$

Für mich ist dies die befriedigendste Ressource, die aus einer einzigen Seite besteht, die ich seit langer Zeit gefunden habe.