Wersja optymalizacyjna problemów decyzyjnych

Wiadomo, że każdy problem optymalizacji / wyszukiwania ma równoważny problem decyzyjny. Na przykład problem najkrótszej ścieżki

• Optymalizacja / Wersja: Biorąc pod uwagę nieukierunkowane nieważony wykres a dwa wierzchołki , znajdowanie najkrótszej ścieżki pomiędzy i .$G = (V, E)$$v,u\in V$$v$$u$
• wersja decyzyjna: Biorąc pod uwagę nieukierowany wykres nieważony , dwa wierzchołki i nieujemną liczbę całkowitą , czy istnieje ścieżka w między i której długość wynosi co najwyżej ?$G = (V, E)$$v,u\in V$$k$$G$$u$$v$$k$

Ogólnie „Znajdź st !” staje się „Czy jest x \ w X st f (x) \ leq k ?”.$x^*\in X$$f(x^*) = \min\{f(x)\mid x\in X\}$$x\in X$$f(x) \leq k$

Ale czy jest też odwrotnie, tj. Czy istnieje równoważny problem optymalizacji dla każdego problemu decyzyjnego? Jeśli nie, jaki jest przykład problemu decyzyjnego, który nie ma równoważnego problemu optymalizacji?

Jak już wspomniano w komentarzach, jak zwykle zależy to od definicji. Moja próba odpowiedzi na to wymaga kilku definicji, więc będzie to kolejny przykład mojej niezdolności do udzielania zwięzłych odpowiedzi.

Definicja: problem optymalizacji jest krotką z$(X,F,Z,\odot)$

• $X$ zestaw odpowiednio zakodowanych (ciągów) instancji lub danych wejściowych .
• F x ∈ X F ( x ) $F$ jest funkcją, która odwzorowuje każdy przypadek dla zestawu z możliwych rozwiązań, z .$x\in X$$F(x)$$x$
• Z ( x , y ) x ∈ X y ∈ F ( x ) Z ( x , y ) $Z$ jest celem funkcja odwzorowuje każdą parę , gdzie i do liczby rzeczywistej zwana wartość z .$(x, y)$$x \in X$$y\in F(x)$$Z(x, y)$$y$
• ⊙ min. $\odot$ to kierunek optymalizacji , lub .$\min$$\max$

Definicja: optymalne rozwiązanie o przykład o problem optymalizacyjny jest możliwe rozwiązanie w którym . Wartość optymalnego rozwiązania jest oznaczona i nazywana optymalną .x ∈ X P O y ∈ F ( x ) Z ( x , y ) = ⊙ { Z ( x , y ′ ) ∣ y ′ ∈ F ( x ) } O p t ( x $x\in X$$P_O$$y\in F(x)$$Z(x, y)=\odot\{Z(x, y')\mid y'\in F(x)\}$$Opt(x)$

Definicja: błąd oceny oznaczoną , odpowiadające problemu optymalizacji się następująco: Dla danej instancji , obliczyć , jeśli jest rozwiązanie optymalne i wyjście „nie optymalne rozwiązanie” w inny sposób.P E P O x ∈ X O p t ( x ) $P_E$$P_O$$x\in X$$Opt(x)$$x$

Pamiętaj, że wymaga to jedynie wartości optymalnego rozwiązania, a nie całego rozwiązania ze wszystkimi szczegółami.

Definicja: problem decyzyjny , oznaczoną odpowiadający problem optymalizacji jest następujący: Z uwagi pary , gdzie i zdecydować, czy ma rozwiązanie dopuszczalne taki, że if i taki, że if .$P_D$$P_O$$(x, k)$$x\in X$$k\in\mathbb{Q}$$x$$y$$Z(x, y)\le k$$\odot=\min$$Z(x, y)\ge k$$\odot=\max$

Pierwszą obserwacją jest teraz, że . Dowód nie jest tutaj trudny i pominięty.$P_O\in \mathrm{NPO} \Rightarrow P_D\in \mathrm{NP}$

Teraz intuicyjnie P E i P D odpowiadające P O nie są trudniejsze niż samo P O. Aby wyrazić to uczucie formalnie (wyznaczając tym samym co równoważne ma oznaczać) użyjemy redukcje.$P_E$$P_D$$P_O$$P_O$

Przypomnijmy, że język L 1 jest czasem wielomianowym redukowalnym do innego języka L 2, jeśli istnieje funkcja f , obliczalna w czasie wielomianowym, tak że dla wszystkich słów x , x ∈ L 1 ⇔ f ( x ) ∈ L 2 . Ten rodzaj jest znany jako redukowalnością Karp lub wiele-do-jednego redukowalnością i jeżeli L 1 jest zredukować do L 2 w ten sposób, to wyrazić przez zapisanie L 1 ≤ m L $L_1$$L_2$$f$$x$$x\in L_1\Leftrightarrow f(x)\in L_2$$L_1$$L_2$$L_1\le_m L_2$. Jest to centralna koncepcja w definicji kompletności NP.

Niestety, redukcje „jeden do jednego” występują między językami i nie jest jasne, jak je stosować w kontekście problemów związanych z optymalizacją. Dlatego musimy rozważyć inny rodzaj redukowalności, redukcję Turinga . Najpierw potrzebujemy tego:

Definicja: wyrocznią dla problemu P oznacza grupę (hipotetyczny) podprogramu, który może rozwiązać wystąpienia P w stałym czasie.$P$$P$

Definicja: Problem P 1 jest wielomianem czasie Turinga sprowadza się do problemu P 2 , napisany P 1 ≤ T P 2 , w przypadku wystąpienia P 1 może być rozwiązany w czasie wielomianowym przez algorytm dostępu do ORACLE P 2 .$P_1$$P_2$$P_1\le_T P_2$$P_1$$P_2$

Nieformalnie, podobnie jak w przypadku ≤ m , relacja P 1 ≤ T P 2 wyraża, że P 1 nie jest trudniejsze niż P 2 . Łatwo też zauważyć, że jeśli P 2 można rozwiązać w czasie wielomianowym, to również P 1 . Ponownie ≤ T jest relacją przechodnią. Następujący fakt jest oczywisty:$\le_m$$P_1\le_T P_2$$P_1$$P_2$$P_2$$P_1$$\le_T$

Niech P O ∈ N P O , wtedy P D ≤ T P E ≤ T P O .$P_O\in \mathrm{NPO}$$P_D\le_T P_E\le_T P_O$

Ponieważ biorąc pod uwagę pełne rozwiązanie, obliczenie jego wartości i podjęcie decyzji, czy spełnia ona wyznaczone k, jest proste.$k$

Definicja: Jeżeli dla dwóch problemów P 1 i P 2 obie zależności P 1 ≤ T P 2 , P 2 ≤ P 1 trzymają, zapisujemy P 1 ≡ T P 2 ; nasze pojęcie równoważności .$P_1$$P_2$$P_1\le_T P_2$$P_2\le P_1$$P_1\equiv_T P_2$

Jesteśmy teraz gotowi, aby udowodnić, że P D ≡ T P E, biorąc pod uwagę odpowiedni problem optymalizacji, to P O ∈ N P O, a Z jest wartością całkowitą. Musimy wykazać, że P E ≤ T P D utrzymuje się. Można określić ⊙ { Z ( x , y ) | Y ∈ F ( x ) } z binarnym wyszukiwania usign z orcale dla P D . Definicję N$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}$ zapewnia, że | Z(x,y) | ≤ 2 q ( | x | ) dla niektórych wielomianówq, więc liczba kroków w wyszukiwaniu binarnym jest wielomianowa w | x | . $|Z(x, y)|\le 2^{q(|x|)}$$q$$|x|$$\Box$

W przypadku problemu optymalizacji P O stosunek do P E jest mniej wyraźny. W wielu przypadkach, betonu, można pokazać, że bezpośrednio P D ≡ T P E ≡ T P O . Aby udowodnić, że ogólnie dotyczy to podanych tutaj ram, potrzebujemy dodatkowego założenia.$P_O$$P_E$$P_D\equiv_T P_E \equiv_T P_O$

Najpierw musimy rozszerzyć ≤ m z par języków na pary odpowiednich problemów decyzyjnych. Łatwo więc zauważyć, że ≤ T jest bardziej ogólne niż ≤ m .$\le_m$$\le_T$$\le_m$

Niech P i P ' być problemy decyzyjne; następnie P ≤ m P ′ ⇒ P ≤ T P ′ . Dzieje się tak, ponieważ redukcję wiele do jednego można interpretować jako korzystanie z wyroczni w bardzo ograniczony sposób: wyrocznia jest wywoływana raz, na samym końcu, a jej wynik jest również zwracany jako wynik ogólny. $P$$P'$$P\le_m P' \Rightarrow P\le_T P'$$\Box$

Teraz jesteśmy gotowi do finału:

Niech P O ∈ N P O i załóżmy, że Z jest liczbą całkowitą o wartościach a P D jest NP-zupełny, a P D ≡ T P E ≡ T P O . Z wcześniejszych obserwacji pozostaje pokazać P ö ≤ T P E . Aby to zrobić, będziemy wykazywać problem P ' O ∈ N P O takie, że P O ≤ T P ' E . Następnie mamy$P_O\in \mathrm{NPO}$$Z$$P_D$

Teraz szczegóły: Zakładamy, że wykonalne roztwory P O, są kodowane za pomocą alfabetu Ď wyposażony w zupełny kolejności. Niech w 0 , w 1 , … będą wyrazami z Σ ∗ wymienionymi w kolejności od nie malejącej długości i porządku leksykograficznego w blokach słów o wspólnej długości. (Zatem w 0 jest pustym słowem.) Dla wszystkich y ∈ Σ ∗ niech σ ( y ) oznacza unikalną liczbę całkowitą i taką, że y = w i . Oba $P_O$$\Sigma$$w_0, w_1, \ldots$$\Sigma^*$$w_0$$y\in\Sigma^*$$\sigma(y)$$i$$y=w_i$$\sigma$i σ - 1 można obliczyć w czasie wielomianowym. Niech q będzie wielomianem takim, że dla wszystkich x ∈ X i wszystkich y ∈ F ( x ) mamy σ ( y ) < 2 q ( | x | ) .$\sigma^{-1}$$q$$x\in X$$y\in F(x)$$\sigma(y)<2^{q(|x|)}$

Teraz problem P ' O jest identyczny jak P O, z wyjątkiem zmodyfikowanej funkcji celu Z ' . Dla x ∈ X i y ∈ F ( x ) bierzemy Z ′ ( x , y ) = 2 q ( | x | ) ⋅ Z ( x , y ) + σ ( y ) . Z $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'$to obliczeniowy czas wielomianu zatem P ' O ∈ N P O .$P_O'\in \mathrm{NPO}$

Aby pokazać, że P O ≤ T P ' E widzimy, że x jest wykonalne dla P O , wtedy i tylko wtedy, gdy jest to wykonalne dla P ' E . Możemy założyć, że tak jest, ponieważ odwrotna sprawa jest łatwa w obsłudze.$P_O\le_T P_E'$$x$$P_O$$P_E'$

Podstawienie Z ' dla Z jest monotoniczne w tym sensie, że dla wszystkich y 1 , y 2 ∈ F ( x ) , jeśli Z ( x , y 1 ) < Z ( x , y 2 ) to Z ' ( x , y 1 ) < Z ′ ( x , y 2 ) . Oznacza to, że każde optymalne rozwiązanie dla $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$w P ' O jest rozwiązaniem optymalnym w x w P O . Zatem nasze zadanie sprowadza się do obliczania rozwiązanie optymalne Y w X w P ' O .$P_O'$$x$$P_O$$y$$x$$P_O'$

Zapytając o wyrocznię dla P ′ E , możemy uzyskać wartość Z ′ ( x , y ) = 2 q ( | x | ) ⋅ Z ( x , y ) + σ ( y ) . Utworzenie reszty tej liczby modulo 2 q ( | x | ) daje σ ( y ), z którego y można obliczyć w czasie wielomianowym.$P_E'$$Z'(x,y)=2^{q(|x|)}\cdot Z(x,y)+\sigma(y)$$2^{q(|x|)}$$\sigma(y)$$y$

As the comments say, the answer depends on the exact definitions. Let me interpret the question in a very basic (even naïve) way.

Let $S$ be some relation, that is $S \subseteq \{ (a,b) \mid a,b \in \Sigma^*\}$.

Now we define a search problem for $S$:

Given $a$, find a $b$ such that $(a,b) \in S$.

and a decision problem for $S$:

Given $(a,b)$ answer whether or not $(a,b) \in S$.

_{(for instance, in the example given in the question, $S$ will hold all the pairs $(u,v,k)$ such that there exists a path between $u$ and $v$ which is shorter than $k$.)}

Note that these two problems are well defined. For this definition, we can ask whether the two problems are "equivalent" for any $S$. In "equivalent" I mean that if one of them is computable (i.e., there exists an algorithm that solves it) than the other one is computable as well. In general, they are not.

Claim 1: Decision implies Search.

Proof: Let $D_S$ be the algorithm that solves the decision problem of $S$. Given an input $a$, We can run $D_S(a,x)$ for any $x\in \Sigma^*$, one after the other, or in parallel. If there exists $b$ such that $(a,b)\in S$, we will eventually find it. If not, the algorithm might not stop$^\dagger$.

Claim 2: Search does not imply Decision.

The reason is that the search algorithm might return a different $b$ than the one we need. That is, for every $a$ there is some $b$ that is very easy to find, but other $b'$ that is not. For instance, let $L$ be some undecidable language, then define

$^\dagger$ This depends on $S$. If, for instance, $S$ is bounded, there might exists an algorithm that does stop.