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 st ?”. $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?

— Luke Miles
źródło

Czy ten bit jest równy zero?

— JeffE

Musisz bardziej szczegółowo wyjaśnić „ekwiwalent”, np. Czy masz na myśli, że jeden można rozwiązać za pomocą drugiego jako wyroczni / czarnej skrzynki w czasie wielomianowym (lub w przestrzeni logarytmicznej)? Czy zależy Ci na wszystkich problemach, czy tylko na problemach

NP $\sf{NP}$ ?

— Kaveh

W zależności od twojego punktu widzenia pytanie jest albo trywialne (podejmij dowolny problem decyzyjny, który nie ma „ ”), albo nie odpowiada (jak udowodnić, że „nie ma równoważnego problemu optycznego”?).

k $k$

— Raphael

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$ jest funkcją, która odwzorowuje każdy przypadek dla zestawu z możliwych rozwiązań, z . $x\in X$ $F(x)$ $x$
$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$
$\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\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\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 i odpowiadające nie są trudniejsze niż samo 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 jest czasem wielomianowym redukowalnym do innego języka jeśli istnieje funkcja , obliczalna w czasie wielomianowym, tak że dla wszystkich słów , . Ten rodzaj jest znany jako redukowalnością Karp lub wiele-do-jednego redukowalnością i jeżeli jest zredukować do w ten sposób, to wyrazić przez zapisanie $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 oznacza grupę (hipotetyczny) podprogramu, który może rozwiązać wystąpienia w stałym czasie. $P$ $P$

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

Nieformalnie, podobnie jak w przypadku , relacja wyraża, że nie jest trudniejsze niż . Łatwo też zauważyć, że jeśli można rozwiązać w czasie wielomianowym, to również . Ponownie 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 , wtedy . $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 jest proste. $k$

Definicja: Jeżeli dla dwóch problemów i obie zależności , trzymają, zapisujemy ; 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 biorąc pod uwagę odpowiedni problem optymalizacji, to a jest wartością całkowitą. Musimy wykazać, że utrzymuje się. Można określić z binarnym wyszukiwania usign z orcale dla . Definicję $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 dla niektórych wielomianów, więc liczba kroków w wyszukiwaniu binarnym jest wielomianowa w. $|Z(x, y)|\le 2^{q(|x|)}$ $q$ $|x|$ $\Box$

W przypadku problemu optymalizacji stosunek do jest mniej wyraźny. W wielu przypadkach, betonu, można pokazać, że bezpośrednio . 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ć z par języków na pary odpowiednich problemów decyzyjnych. Łatwo więc zauważyć, że jest bardziej ogólne niż . $\le_m$ $\le_T$ $\le_m$

Niech i być problemy decyzyjne; następnie . 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 i załóżmy, że jest liczbą całkowitą o wartościach a jest NP-zupełny, a Z wcześniejszych obserwacji pozostaje pokazać . Aby to zrobić, będziemy wykazywać problem takie, że . Następnie mamy $P_O\in \mathrm{NPO}$ $Z$ $P_D$

P D \equiv T P E \equiv T P O .

$P_D\equiv_T P_E \equiv_T P_O.$

PO≤TPE $P_O\le_T P_E$

P′O∈NPO $P_O'\in \mathrm{NPO}$

PO≤TP′E $P_O\le_T P_E'$

Drugi i trzeci

zachowują ze względu na równoważność wcześniejszej wersji decyzji i oceny. Trzecia

wynika z NP-kompletności

i dwóch wspomnianych wcześniej faktów, mianowicie

P O \leq T P' E \leq T P' D \leq T P D \leq T P E .

$P_O\le_T P_E' \le_T P_D'\le_T P_D\le_T P_E.$

≤T $\le_T$

PD $P_D$

PO∈NPO⇒PD∈NP $P_O\in \mathrm{NPO} \Rightarrow P_D\in \mathrm{NP}$

.P≤mP′O⇒P≤TP′O $P\le_m P_O' \Rightarrow P\le_T P_O'$

Teraz szczegóły: Zakładamy, że wykonalne roztwory są kodowane za pomocą alfabetu wyposażony w zupełny kolejności. Niech 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 jest pustym słowem.) Dla wszystkich niech oznacza unikalną liczbę całkowitą taką, że . Oba $P_O$ $\Sigma$ $w_0, w_1, \ldots$ $\Sigma^*$ $w_0$ $y\in\Sigma^*$ $\sigma(y)$ $i$ $y=w_i$ $\sigma$ i można obliczyć w czasie wielomianowym. Niech będzie wielomianem takim, że dla wszystkich i wszystkich mamy . $\sigma^{-1}$ $q$ $x\in X$ $y\in F(x)$ $\sigma(y)<2^{q(|x|)}$

Teraz problem jest identyczny jak z wyjątkiem zmodyfikowanej funkcji celu . Dla i bierzemy . $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'\in \mathrm{NPO}$

Aby pokazać, że widzimy, że jest wykonalne dla , wtedy i tylko wtedy, gdy jest to wykonalne dla . 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 dla jest monotoniczne w tym sensie, że dla wszystkich , jeśli to . 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 jest rozwiązaniem optymalnym w w . Zatem nasze zadanie sprowadza się do obliczania rozwiązanie optymalne w w . $P_O'$ $x$ $P_O$ $y$ $x$ $P_O'$

Zapytając o wyrocznię dla , możemy uzyskać wartość . Utworzenie reszty tej liczby modulo daje z którego 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$

— uli
źródło

„Wyrocznia dla problemu P jest (hipotetyczną) podprogramem, który może rozwiązywać przypadki P w stałym czasie”. Czy wyrocznia musi trwać tylko przez cały czas?

— Tim

@Tim Oczywiście są książki, wymieniłem kilka w komentarzach do innej odpowiedzi

— uli

@Tim chodzi wyroczni: Jeśli znalazłeś / pomyślany zmniejszenie

pomiędzy dwoma problemami

zostały zmniejszone problem znalezienia skutecznego algorytmu

do znalezienia skutecznego algorytmu

. Albo innymi słowy redukcja informuje, że w celu rozwiązania

można użyć

. To jest tak jak z podprogramu do

w algorytmie

. Jednak problemy

A≤TB $A\le_T B$

A $A$

B $B$

A $A$

B $B$

A $A$

B $B$

A $A$

B $B$ are often problems where we don’t know efficient solutions. And in case of Turing-reducibility we even use it in cases where the problems involved aren’t decidable at all.

— uli

@Tim Thus

$B$ is an unknown subroutine. It has become a custom in complexity theory to call the hypothetical algorithm for

$A$ derived from the reduction as an algorithm with oracle $B$ . Calling the unknown subroutine for

$B$ an oracle just expresses that we can’t hope to find an efficient algorithm for

$B$ just as we can’t hope to obtain an oracle for

$B$ . This choice is somewhat unfortunate, as it connotes a magical ability. The cost for the oracle should be

$|x|$ as a subroutine has at least to read the input

$x$ .

— uli

An excellent answer all around; the only thing I would add (coming at it now via another question) is that the 'optimization direction' is a needless bit of complexity and for concreteness we can always presume that the objective function

$Z$ is to be maximized; if the intention is to minimize, then we can just define a new objective function

$Z'=-Z$ and rewrite all the minimization of

$Z$ as maximization of

$Z'$ .

— Steven Stadnicki

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

$S = \{ (x,0) \mid x\in \Sigma^*\} \cup \{ (x,1) \mid x \in L\}.$ For every

$x$ the search algorithm can return

$0$ . But no decision algorithm can answer correctly whether

$(x,1) \in S$ , for all the pairs

$(x,1)$ . If it could, it would have decided an undecidable problem, which is impossible.

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

— Ran G.
źródło

The right decision problem is existence of

$b$ s.t.

$\langle a,b \rangle \in S$ .

— Kaveh

If decision is defined as the existence of

$b$ , then search implies decision.

— Ran G.

In a weak sense, i.e. w.r.t. computability but not complexity is a more delicate issue.

— Kaveh