Funktionsprobleme und

Es fällt mir schwer, formale Definitionen von Funktionskomplexitätsklassen zu finden. Hier sind zwei aus Wikipedia.

Eine binäre Beziehung ist genau dann in FP, wenn es einen deterministischen Polynomzeitalgorithmus gibt, der bei gegebenem etwas finden kann, so dass gilt.$P(x,y)$$x$$y$$P(x,y)$

Die obige Definition scheint zu implizieren, dass für alle Beziehungen in FP gilt, dass für jedes mindestens ein , dessen Länge in der Länge von polynomisch ist . Es scheint jedoch nicht einzuschränken, dass für dieses mehr existiert , so dass gilt, während exponentiell länger als .$x$$y$$x$$y$$x$$P(x,y)$$y$$x$

Eine binäre Beziehung , in der höchstens polynomiell länger als , liegt genau dann in FNP vor, wenn es einen deterministischen Polynomzeitalgorithmus gibt, der bestimmen kann, ob sowohl für als auch für .$P(x,y)$$y$$x$$P(x,y)$$x$$y$

Diese Definition impliziert, dass für eine Beziehung in FNP nicht wahr sein muss, dass für jedes mindestens ein existiert , damit gilt. Dies impliziert jedoch, dass wenn gilt, höchstens polynomiell länger als .$y$$x$$P(x,y)$$P(x,y)$$y$$x$

In der Literatur kann man lesen, dass FP FNP . Soweit ich verstehe (oder nicht verstehe), kann dies nicht wahr sein. Es ist möglich, dass für eine Beziehung FP ein so dass gilt und exponentiell länger als . Aus diesem Grund gehört diese Beziehung nicht zu FNP und daher zu FP FNP .$\subseteq$ $R(x,y) \in$ $(x,y)$$R(x,y)$$y$$x$ $\not\subseteq$

Sind die Definitionen auf Wikipedia unvollständig? Vermisse ich etwas

Wie auch immer, was sind einige gute Quellen, um sich über Funktionsprobleme zu informieren (ich glaube, ich kenne mich mit Entscheidungsproblemen aus)?

Ich fand Folgendes in Papadimitrious Buch Computational Complexity, das ich als befriedigend empfand.

Sei eine binäre Beziehung auf Strings.$R \subseteq \Sigma^* \times \Sigma^*$

$R$ heißt polynomiell entscheidbar, wenn es eine deterministische Turingmaschine gibt, die die Sprache in Polynomzeit entscheidet.$\{x;y : (x,y) \in R\}$

Wir sagen , dass ist polynomial ausgeglichen , wenn bedeutet für einige .$R$$(x,y) \in R$$|y| \leq |x|^k$$k \geq 1$

Dann bemerkt Papadimitriou Folgendes, was im Grunde eine andere Definition für NP ist :

Sei eine Sprache. NP genau dann, wenn es eine polynomiell entscheidbare und polynomiell ausgeglichene Beziehung , so dass für einige .$L \subseteq \Sigma^*$$L \in$ $R$$L = \{x : (x,y) \in R$$y \}$

Ein paar Dutzend Seiten später ...

Das mit [ NP ] verbundene Funktionsproblem, bezeichnet mit [hier steht für die Sprache, nicht für den Logspace], ist das folgende Rechenproblem:$L$$\in$ $FL$$L$

Gegeben , finden einen String , so dass , wenn eine solche Zeichenfolge vorhanden ist ; Wenn keine solche Zeichenfolge vorhanden ist, geben Sie "no" zurück.$x$$y$$R_L(x,y)$

Dann

Die Klasse aller Funktionsprobleme, die wie oben mit Sprachen in NP verbunden sind, heißt FNP . FP ist die resultierende Unterklasse, wenn wir nur Funktionsprobleme in FNP berücksichtigen , die in Polynomzeit gelöst werden können.

Vergessen wir die Wikipedia-Definitionen und lassen uns unsere eigenen einfallen.

Eine Funktion befindet sich in wenn es eine Polytime-Turing-Maschine gibt, die bei Eingabe ausgibt .$f$$\mathsf{FP}$$x$$f(x)$

Eine Funktion befindet sich in wenn:$f$$\mathsf{FNP^\ast}$

1. Die Funktion ist polynomiell begrenzt: Es existiert ein Polynom so dass .$f$$p$$|f(x)| \leq p(|x|)$

2. Es gibt eine Polytime-Turing-Maschine, die mit bestimmt, ob .$x,y$$f(x)=y$

Wenn in ist, ist es definitiv polynomiell begrenzt. Da wir in Polynomzeit berechnen können können wir bei berechnen und mit vergleichen , alles in Polynomzeit.$f$$\mathsf{FP}$$f(x)$$x,y$$f(x)$$y$

den Komplexitätszoo , scheint es, dass tatsächlich eine andere Definition hat und dass zwei verschiedene und inkompatible Definitionen hat, von denen eine die oben angegebene ist.$\mathsf{FNP}$$\mathsf{FP}$

Ich möchte einen weiteren Satz von Definitionen aus Automata, Computability and Complexity von Elaine Rich hinzufügen .

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

Die Klasse FNP : Eine binäre Beziehung befindet sich in wenn es einen deterministischen Polynomzeitprüfer gibt, der bei einem beliebigen Eingabepaar bestimmt, ob . Entsprechend ist in wenn es einen nichtdeterministischen Polynomzeitalgorithmus gibt, der bei einer beliebigen Eingabe einige finden kann, so dass$Q$$\mathsf{FNP}$$(x,y)$$(x,y) \in Q$$Q$$\mathsf{FNP}$$x$$y$$(x,y) \in Q$

Dies unterscheidet sich nur geringfügig von den Definitionen auf Wikipedia, impliziert jedoch andere Dinge. Am wichtigsten ist , Elaine Rich ihre Definition von bedeutet nicht , dass , wenn , hat sein Polynom in . Es ist wahrscheinlich, dass die Wiki-Definitionen schlampige Kopien davon sind.$\mathsf{FNP}$$(x,y) \in Q$$y$ $x$

Aus diesen Definitionen geht klarer hervor, dass .$\mathsf{FP} \subseteq \mathsf{TFNP} \subseteq \mathsf{FNP}$