Optimierungsversion von Entscheidungsproblemen

Es ist bekannt, dass jedes Optimierungs- / Suchproblem ein äquivalentes Entscheidungsproblem hat. Zum Beispiel das Problem mit dem kürzesten Weg

• Optimierungs- / Suchversion: Finden Sie bei einem ungerichteten ungewichteten Graphen $G = (V, E)$ und zwei Eckpunkten $v,u\in V$ einen kürzesten Weg zwischen $v$ und $u$ .
• Entscheidungsversion: Gibt es bei einem ungerichteten ungewichteten Graphen $G = (V, E)$ , zwei Eckpunkten $v,u\in V$ und einer nicht negativen ganzen Zahl $k$ in G einen Pfad $G$zwischen $u$ und $v$ dessen Länge höchstens k beträgt $k$?

$x^*\in X$$f(x^*) = \min\{f(x)\mid x\in X\}$$x\in X$$f(x) \leq k$

Gilt aber auch das Gegenteil, dh gibt es für jedes Entscheidungsproblem ein gleichwertiges Optimierungsproblem? Wenn nicht, was ist ein Beispiel für ein Entscheidungsproblem, bei dem es kein gleichwertiges Optimierungsproblem gibt?

Wie bereits in den Kommentaren ausgeführt, kommt es wie gewohnt auf die Definitionen an. Mein Versuch, dies zu beantworten, erfordert einige Definitionen. Dies wird ein weiteres Beispiel dafür sein, dass ich keine präzisen Antworten geben kann.

Definition: Ein Optimierungsproblem ist ein Tupel $(X,F,Z,\odot)$ mit

• $X$ die Menge der entsprechend codierten Instanzen oder Eingaben (Strings) .
• F x ∈ $F$ ist eine Funktion, die jede Instanz auf eine Menge von möglichen Lösungen von abbildet .$x\in X$ F ( x ) $F(x)$$x$
• Z ( x , y ) x ≤ X y ≤ F ( x $Z$ ist die Zielfunktion, die jedes Paar , wobei und , auf eine reelle Zahl abbildet, die als Wert von .$(x, y)$$x \in X$$y\in F(x)$ Z ( x , y ) $Z(x, y)$$y$
• $\odot$ ist die Optimierungsrichtung , entweder oder .$\min$$\max$

Definition: Eine optimale Lösung einer Instanz eines Optimierungsproblems ist eine mögliche Lösung für die . Der Wert einer optimalen Lösung wird mit und als Optimum bezeichnet .$x\in X$$P_O$$y\in F(x)$$Z(x, y)=\odot\{Z(x, y')\mid y'\in F(x)\}$$Opt(x)$

Definition: Das Auswertungsproblem , bezeichnete , entsprechend das Optimierungsproblem ist folgende: Da eine Instanz , compute , wenn eine optimale Lösung und Ausgang „keine optimale Lösung“ sonst hat.$P_E$$P_O$$x\in X$$Opt(x)$$x$

Beachten Sie, dass hierbei nur der Wert der optimalen Lösung abgefragt wird, nicht die gesamte Lösung selbst mit all ihren Details.

Definition: Das Entscheidungsproblem , bezeichnete für das Optimierungsproblem entsprechendes ist folgende: Bei einem PaarP D P A ( x , k ) x ∈ X k ∈ Q x y Z ( x , y ) ≤ k ⊙ = min Z ( x , y ) ≥ k ⊙ = $P_D$$P_O$$(x, k)$ , wobei und , entscheiden , ob einen realisierbare Lösung hat so dass wenn und so dass wenn .$x\in X$$k\in\mathbb{Q}$$x$$y$$Z(x, y)\le k$$\odot=\min$$Z(x, y)\ge k$$\odot=\max$

Eine erste Beobachtung ist jetzt, dass . Der Beweis ist hier nicht schwierig und entfällt.$P_O\in \mathrm{NPO} \Rightarrow P_D\in \mathrm{NP}$

Jetzt intuitiv und zu entsprechenden ist nicht schwieriger als selbst. Um dieses Gefühl formal auszudrücken (und damit zu definieren, was Äquivalent bedeuten soll), werden wir Reduktionen verwenden.P E P D P O P $P_E$$P_D$$P_O$$P_O$

Man erinnere sich, dass eine Sprache polynomial auf eine andere Sprache reduzierbar ist, wenn es eine FunktionL 1 L 2 f x x ∈ L 1 ⇔ f ( x ) ∈ L 2 L 1 L 2 L 1 ≤ m L $L_1$$L_2$$f$ in polynomischer Zeit berechenbare gibt, so dass für alle Wörter , . Diese Art der Reduzierbarkeit ist als Karp oder als 1: 1-Reduzierbarkeit bekannt . Wenn auf diese Weise auf reduzierbar ist, wir dies aus, indem wir . Dies ist ein zentrales Konzept bei der Definition der NP-Vollständigkeit.$x$$x\in L_1\Leftrightarrow f(x)\in L_2$$L_1$$L_2$$L_1\le_m L_2$

Leider gibt es viele Eins-zu-Eins-Reduzierungen zwischen den Sprachen, und es ist nicht klar, wie sie im Kontext von Optimierungsproblemen eingesetzt werden sollen. Daher müssen wir eine andere Art von Reduzierbarkeit in Betracht ziehen, die Turing-Reduzierbarkeit . Zuerst brauchen wir das:

Definition: Ein Orakel für ein Problem ist eine (hypothetische) Subroutine, die Instanzen von in konstanter Zeit lösen kann .P $P$$P$

Definition: Ein ProblemP 1 P 2 P 1 ≤ T P 2 P 1 P $P_1$ ist polynomial-time Turing-reducible zu einem Problem , geschrieben , wenn Instanzen von in polynomialer Zeit durch einen Algorithmus mit Zugriff auf ein Orakel für gelöst werden können .$P_2$$P_1\le_T P_2$$P_1$$P_2$

Informell, genau wie bei , die Beziehung≤ m P 1 ≤ T P 2 P 1 P 2 P 2 P 1 ≤ $\le_m$$P_1\le_T P_2$ ausgedrückt aus, dass nicht schwieriger ist als . Es ist auch leicht zu erkennen, dass wenn in Polynomzeit gelöst werden kann, auch . Wieder ist eine transitiven Beziehung. Die folgende Tatsache ist offensichtlich:$P_1$$P_2$$P_2$$P_1$$\le_T$

Lassen Sie und dann .$P_O\in \mathrm{NPO}$$P_D\le_T P_E\le_T P_O$

Weil es angesichts der vollständigen Lösung einfach ist , ihren Wert zu berechnen und zu entscheiden, ob sie die Grenze erfüllt .$k$

Definition: Wenn für zwei Probleme und$P_1$$P_2$ beide Relationen , gelten, schreiben wir ; unser Begriff der Äquivalenz .$P_1\le_T P_2$$P_2\le P_1$$P_1\equiv_T P_2$

Wir sind jetzt bereit zu beweisen, dass , , das entsprechende Optimierungsproblem ist und ist ein ganzzahliger Wert. Wir müssen zeigen, dass gilt. Wir können mit einer binären Suche bestimmen, indem wir die Orcale für . Die Definition von stellt das sicher$P_D\equiv_T P_E$$P_O\in \mathrm{NPO}$$Z$$P_E \le_T P_D$$\odot\{Z(x,y)\mid y\in F(x)\}$$P_D$$\mathrm{NPO}$$|Z(x, y)|\le 2^{q(|x|)}$ für ein Polynom , so dass die Anzahl der Schritte in der binären Suche in polynomisch ist . $q$$|x|$$\Box$

Für ein Optimierungsproblem $P_O$ die Beziehung zu weniger klar. In vielen konkreten Fällen kann man direkt zeigen, dass . Um zu beweisen, dass dies im Allgemeinen innerhalb des hier gegebenen Rahmens gilt, benötigen wir eine zusätzliche Annahme.$P_E$$P_D\equiv_T P_E \equiv_T P_O$

Zuerst müssen wir erweitern $\le_m$ von Sprachpaaren auf Paare der entsprechenden Entscheidungsprobleme erweitern. Dann ist leicht zu erkennen, dass allgemeiner ist als .$\le_T$$\le_m$

Sei$P$ und Entscheidungsprobleme; dann . Dies gilt, weil eine Eins-zu-Eins-Reduktion so interpretiert werden kann, dass ein Orakel nur sehr eingeschränkt genutzt wird: Das Orakel wird ganz am Ende einmal aufgerufen, und sein Ergebnis wird auch als Gesamtergebnis zurückgegeben. $P'$$P\le_m P' \Rightarrow P\le_T P'$$\Box$

Jetzt sind wir bereit für das Finale:

Es sei und angenommen, ist ganzzahlig und ist NP-vollständig, dannBei den vorherigen Beobachtungen bleibt zu zeigen . Dazu zeigen wir ein Problem so dass . Dann haben wirDas zweite und dritte gelten wegen der Gleichwertigkeit der zuvor Entscheidungs- und Evaluierungsversion. Das dritte ergibt sich aus der NP-Vollständigkeit von und den beiden zuvor genannten Tatsachen, nämlich$P_O\in \mathrm{NPO}$$Z$$P_D$

Nun die Details: Angenommen, die möglichen Lösungen von werden mit einem Alphabet codiert, das mit einer Gesamtreihenfolge ausgestattet ist. Sei die Wörter aus die in der Reihenfolge nicht abnehmender Länge und lexikografischer Reihenfolge in den Wortblöcken mit gemeinsamer Länge aufgelistet sind. (Also ist das leere Wort.) Für alle sei die eindeutige ganze Zahl so dass . Sowohl als auch und alle wir haben$P_O$$\Sigma$$w_0, w_1, \ldots$$\Sigma^*$$w_0$$y\in\Sigma^*$$\sigma(y)$$i$$y=w_i$$\sigma$$\sigma^{-1}$ können in Polynomzeit berechnet werden. Sei ein Polynom, so dass für alle$q$$x\in X$$y\in F(x)$$\sigma(y)<2^{q(|x|)}$ .

Das Problem ist nun identisch mit Ausnahme einer modifizierten Zielfunktion . Für und nehmen wir . ist in Polynomzeit berechenbar, also .$P_O'$$P_O$$Z'$$x\in X$$y\in F(x)$$Z'(x, y)=2^{q(|x|)}\cdot Z(x,y)+\sigma(y)$$Z'$$P_O'\in \mathrm{NPO}$

Um diese zu zeigen beobachten wir , dass für machbar ist , wenn und nur wenn es möglich ist . Wir können davon ausgehen, dass dies der Fall ist, da der umgekehrte Fall trivial zu handhaben ist.$P_O\le_T P_E'$$x$$P_O$$P_E'$

Die Substitution von für ist monoton in dem Sinne, dass für alle , wenn dann . Dies impliziert, dass jede optimale Lösung für in eine optimale Lösung von in . Somit reduziert sich unsere Aufgabe auf die Berechnung einer optimalen Lösung von$Z'$$Z$$y_1, y_2\in F(x)$$Z(x, y_1)<Z(x, y_2)$$Z'(x, y_1)<Z'(x, y_2)$$x$$P_O'$$x$$P_O$$y$$x$ in .$P_O'$

wir das Orakel nach wir den Wert von . Wenn man den Rest dieser Zahl modulo erhält man aus dem in Polynomzeit berechnet werden kann.$P_E'$$Z'(x,y)=2^{q(|x|)}\cdot Z(x,y)+\sigma(y)$$2^{q(|x|)}$$\sigma(y)$$y$

Wie aus den Kommentaren hervorgeht, hängt die Antwort von den genauen Definitionen ab. Lassen Sie mich die Frage sehr grundlegend (sogar naiv) interpretieren.

Sei eine Beziehung, das heißt .$S$$S \subseteq \{ (a,b) \mid a,b \in \Sigma^*\}$

Nun definieren wir ein Suchproblem für S :$S$

Wenn a gegeben ist , finde a b so, dass ( a , b ) ∈ S ist .$a$$b$$(a,b) \in S$

und ein Entscheidungsproblem für S :$S$

Gegeben ( a , b ) Antwort , ob oder nicht ( ein , b ) ∈ S .$(a,b)$$(a,b) \in S$

_{(In dem in der Frage angegebenen Beispiel wird S beispielsweise alle Paare ( u , v , k ) so halten, dass zwischen u und v ein Pfad existiert, der kürzer als k ist .)$S$$(u,v,k)$$u$$v$$k$}

Beachten Sie, dass diese beiden Probleme gut definiert sind . Für diese Definition können wir fragen, ob die beiden Probleme für jedes S "äquivalent" sind . In "Äquivalent" meine ich, dass, wenn einer von ihnen berechenbar ist (dh es gibt einen Algorithmus, der es löst), der andere ebenfalls berechenbar ist. Im Allgemeinen sind sie nicht.$S$

Anspruch 1 : Entscheidung impliziert Suche .

Beweis: Sei D S der Algorithmus, der das Entscheidungsproblem von S löst . Bei einer Eingabe a können wir D S ( a , x ) für jedes x ∈ Σ ∗ nacheinander oder parallel ausführen . Wenn es existiert , b , so dass$D_S$$S$$a$$D_S(a,x)$$x\in \Sigma^*$$b$ ( a , b ) ∈ S ist , werden wir es schließlich finden. Wenn nicht, stoppt der Algorithmus möglicherweise nicht † .$(a,b)\in S$$^\dagger$

Anspruch 2 : Suchen Sie sich nicht bedeuten Entscheidung .

Der Grund ist, dass der Suchalgorithmus möglicherweise ein anderes b zurückgibt als das, das wir benötigen. Das heißt, für jedes a gibt es ein b , das sehr leicht zu finden ist, für das andere b ' jedoch nicht. Nehmen wir zum Beispiel L einige unentscheidbar Sprache sein, dann definieren S = { ( x , 0 ) | x ∈ & Sgr; * } ∪ { $b$$a$$b$$b'$$L$ x , 1 ) | x ∈ L } . Für jedes

† Das hängt von S ab . Wenn zum Beispiel S begrenzt ist, existiert möglicherweise ein Algorithmus, der stoppt.$^\dagger$$S$$S$