Problemy decyzyjne a „rzeczywiste” problemy, które nie są „tak lub nie”

Czytałem w wielu miejscach, że niektóre problemy są trudne do przybliżenia ( NP jest trudne do przybliżenia ). Ale przybliżenie nie jest problemem decyzyjnym: odpowiedź jest liczbą rzeczywistą, a nie Tak lub Nie. Również dla każdego pożądanego współczynnika przybliżenia istnieje wiele odpowiedzi, które są poprawne, a wiele błędnych, a to zmienia się wraz z pożądanym współczynnikiem przybliżenia!

Więc jak można powiedzieć, że ten problem jest trudny NP?

(zainspirowany drugim punktem w Jak trudno policzyć liczbę prostych ścieżek między dwoma węzłami na ukierunkowanym wykresie? )

— Ran G.
źródło

Jak już powiedziałeś, nie musisz podejmować decyzji, więc potrzebne są nowe klasy złożoności i nowe rodzaje redukcji, aby uzyskać odpowiednią definicję twardości NP dla problemów z optymalizacją .

Jednym ze sposobów osiągnięcia tego jest posiadanie dwóch nowych klas NPO i PO, które zawierają problemy z optymalizacją i naśladują oczywiście klasy NP i P dla problemów decyzyjnych. Potrzebne są również nowe redukcje. Następnie możemy odtworzyć wersję twardości NP dla problemów z optymalizacją, tak jak w przypadku problemów decyzyjnych. Ale najpierw musimy ustalić, na czym polega problem optymalizacji .

Definicja: Niech $O=(X,L,f,opt)$ będzie problemem optymalizacyjnym . $X$ jest zbiorem danych wejściowych lub instancji odpowiednio zakodowanych jako łańcuchy. $L$ jest funkcją, która odwzorowuje każdą instancję $x\in X$ na zbiór ciągów, możliwe rozwiązania instancji $x$ . Jest to zestaw, ponieważ istnieje wiele rozwiązań problemu z optymalizacją. Zatem nie mamy funkcji celu $f$ która mówi nam dla każdej pary $(x, y)$ $y\in L(x)$ wystąpienia i rozwiązania jegokosztlubwartość. $opt$ mówi nam, czy maksymalizujemy, czy minimalizujemy.

To pozwala nam zdefiniować, czym jest optymalne rozwiązanie : Niech będzie optymalnym rozwiązaniem wystąpienia problemu optymalizacyjnego z $y_{opt}\in L(x)$ $x\in X$ $O=(X,L,f,opt)$

f (x, y_{o p t}) = o p t {f (x, y^{'}) ∣ y^{'} \in L (x)} .

$f(x,y_{opt})=opt\{f(x,y')\mid y'\in L(x)\}.$ Rozwiązaniem optymalnym jest często oznaczany przez

y^{*}

$y^*$ .

Teraz możemy zdefiniować klasę NPO : Niech $NPO$ będzie zbiorem wszystkich problemów optymalizacyjnych $O=(X,L,f,opt)$ z:

$X\in P$
Istnieje wielomian $p$ z $|y|\le p(|x|)$ dla wszystkich instancji $x\in X$ i wszystkich możliwych rozwiązań $y\in L(x)$ . Ponadto istnieje algorytm deterministyczny, który decyduje w czasie wielomianowym, czy $y\in L(x)$ .
$f$ można oszacować w czasie wielomianowym.

Intuicja za tym stoi:

Możemy skutecznie zweryfikować, czy $x$ jest faktycznie prawidłowym wystąpieniem naszego problemu optymalizacji.
Rozmiar możliwych rozwiązań jest wielomianowo ograniczony wielkością danych wejściowych, i możemy skutecznie zweryfikować, czy jest możliwym do rozwiązania rozwiązaniem wystąpienia . $y\in L(x)$ $x$
Wartość roztworu można skutecznie ustalić. $y\in L(x)$

Odzwierciedla to jak jest zdefiniowana, teraz PO : Niech będzie zbiorem wszystkich problemów z , które mogą być rozwiązane przez deterministycznego algorytmu w czasie wielomianowym. $NP$ $PO$ $NPO$

Obecnie jesteśmy w stanie określić, co chcemy wywołać aproksymacji algorytm : An aproksymacji algorytm na optymalizację bezproblemowych to algorytm oblicza praktycznym rozwiązaniem na przykład, . $O=(X,L,f,opt)$ $y\in L(x)$ $x\in X$

Uwaga: Aby nie pytać o optymalne rozwiązanie, mamy tylko to, co ma wykonalne .

Teraz mamy dwa rodzaje błędów: błąd bezwzględny możliwego rozwiązania instancji problemu optymalizacyjnego wynosi . $y\in L(x)$ $x\in X$ $O=(X,L,f,opt)$ $|f(x,y)-f(x,y^*)|$

Błąd bezwzględny algorytmu aproksymacji nazywamy problemem optymalizacji ograniczonym przez jeśli algorytm oblicza dla każdej instancji możliwe rozwiązanie z błędem bezwzględnym ograniczonym przez . $A$ $O$ $k$ $A$ $x\in X$ $k$

Przykład: Zgodnie z twierdzeniem Vizing indeks chromatyczny wykresu (liczba kolorów w barwieniu krawędzi przy najmniejszej liczbie użytych kolorów) wynosi lub , gdzie jest maksymalnym stopniem węzła. Z dowodu twierdzenia przybliżeniem algorytm może być opracowany, który oblicza krawędź barwieniu kolorów. Odpowiednio mamy algorytm aproksymacyjny dla $\Delta$ $\Delta+1$ $\Delta$ $\Delta+1$ Problem, w którym błąd bezwzględny jest ograniczony przez . $\mathsf{Minimum-EdgeColoring}$ $1$

Ten przykład jest wyjątkiem, małe błędy bezwzględne są rzadkie, dlatego definiujemy błąd względny algorytmu aproksymacji w przypadku problemu optymalizacji z dla wszystkich i będzie $\epsilon_A(x)$ $A$ $x$ $O=(X,L,f,opt)$ $f(x,y)>0$ $x\in X$ $y\in L(x)$

ϵ_{A} (x) := {\begin{cases} 0 & f (x, A (x)) = f (x, y^{*}) \\ \frac{| f (x, A (x)) - f (x, y^{*}) |}{max {f (x, A (x)), f (x, y^{*})}} & f (x, A (x)) \neq f (x, y^{*}) \end{cases}

$\epsilon_A(x):=\begin{cases}0&f(x,A(x))=f(x,y^*)\\\frac{|f(x,A(x))-f(x,y^*)|}{\max\{f(x,A(x)),f(x,y^*)\}}&f(x,A(x))\ne f(x,y^*)\end{cases}$

gdzie jest praktycznym rozwiązaniem obliczane przez przybliżenie algorytm . $A(x)=y\in L(x)$ $A$

Możemy obecnie określić przybliżenie algorytm do optymalizacji bezproblemowych za -approximation algorytm do , że błąd względny jest ograniczona przez dla każdej instancji , a zatem $A$ $O=(X,L,f,opt)$ $\delta$ $O$ $\epsilon_A(x)$ $\delta\ge 0$ $x\in X$

ϵ_{A} (x) \leq δ \forall x \in X .

$\epsilon_A(x)\le \delta\qquad \forall x\in X.$

Wybór w mianowniku definicji błędu względnego został wybrany aby symetryczny definicja dla maksymalizacji i minimalizacji. Wartość błędu względnego . W przypadku problemu maksymalizującego wartość rozwiązania nigdy nie jest mniejsza niż $\max\{f(x,A(x)),f(x,y^*)\}$ $\epsilon_A(x)\in[0,1]$ i nigdy nie większa niż dla zminimalizowania problemu. $(1-\epsilon_A(x))\cdot f(x,y^*)$ $1/(1-\epsilon_A(x))\cdot f(x,y^*)$

Teraz możemy nazwać problem optymalizacji -aprzybliżeniem, jeśli istnieje -algorytm aproksymacji dla który działa w czasie wielomianowym. $\delta$ $\delta$ $A$ $O$

Nie chcemy patrzeć na błąd dla każdej instancji , patrzymy tylko na najgorszy przypadek. W ten sposób definiujemy , maksymalny błąd względny algorytmu aproksymacji dla problemu optymalizacyjnego który ma wynosić $x$ $\epsilon_A(n)$ $A$ $O$

ϵ_{A} (n) = sup {ϵ_{A} (x) ∣ | x | \leq n} .

$\epsilon_A(n)=\sup\{\epsilon_A(x)\mid |x|\le n\}.$

Gdzie powinien być wielkości instancji. $|x|$

Przykład: Maksymalne dopasowanie na wykresie można przekształcić w minimalną pokrywę węzła , dodając wszystkie węzły incydentalne z dopasowania do pokrywy wierzchołków. Tak więc krawędzie są pokryte. Jak każdej pokrywy wierzchołków w tym jedną optymalną musi mieć jeden z węzłów każdej zadaszonym krawędzi, w przeciwnym razie może ulec poprawie, mamy . Wynika z tego, że $C$ $1/2\cdot |C|$ $1/2\cdot |C|\cdot f(x,y^*)$ Zatem chciwi algorytm dopasowaną maksymalnej jest-approximatio algorytm dla. Stądjest-approximable.

\frac{| C | - f (x, y^{*})}{| C |} \leq \frac{1}{2}

$\frac{|C|-f(x,y^*)}{|C|}\le\frac{1}{2}$

1 / 2

$1/2$

M i n i m a l - V e r t e x C o v e r

$\mathsf{Minimal-VertexCover}$

M i n i m a l - V e r t e x C o v e r

$\mathsf{Minimal-VertexCover}$

1 / 2

$1/2$

Niestety błąd względny nie zawsze jest najlepszym pojęciem jakości dla przybliżenia, jak pokazano w poniższym przykładzie:

Przykład: Prosty algorytm zachłanny może aproksymować . Analiza pokazuje, że $\mathsf{Minimum-SetCover}$ a zatembędzie

\frac{| C |}{| C^{*} |} \leq H_{n} \leq 1 + \ln (n)

$\frac{|C|}{|C^*|}\le H_n\le 1+\ln(n)$

M i n i m u m - S e t C o v e r

$\mathsf{Minimum-SetCover}$

Przybliżony

\frac{\ln (n)}{1 + \ln (n)}

$\frac{\ln(n)}{1+\ln(n)}$

Jeśli błąd względny jest bliski korzystna jest następująca definicja. $1$

Niech jest optymalizacja-problem dla wszystkich i i przybliżeniem algorytmu- . Współczynnik aproksymacji możliwego rozwiązania $O=(X,L,f,opt)$ $f(x, y)>0$ $x\in X$ $y\in L(x)$ $A$ $O$ $r_A(x)$ instancji to $A(x)=y\in L(x)$ $x\in X$

r_{A} (x) = {\begin{cases} 1 & f (x, A (x)) = f (x, y^{*}) \\ max {\frac{f (x, A (x))}{f (x, y^{*})}, \frac{f (x, y^{*})}{f (x, A (x))}} & f (x, A (x)) \neq f (x, y^{*}) \end{cases}

$r_A(x)=\begin{cases}1&f(x,A(x))=f(x,y^*)\\\max\left\{ \frac{f(x,A(x))}{f(x, y^*)},\frac{f(x, y^*)}{f(x, A(x))}\right\}&f(x,A(x))\ne f(x,y^*)\end{cases}$

$A$ $r$ $O$ $r_A(x)$ $r\ge1$ $x\in X$

r_{A} (x) \leq r

$r_A(x)\le r$

r

$r$

A

$A$

O

$O$

O

$O$ $r$

r_{A} (n)

$r_A(n)$

r_{A} (n) = sup {r_{A} (x) ∣ | x | \leq n} .

$r_A(n)=\sup\{r_A(x)\mid |x|\le n\}.$

1

$1$

M i n i m u m - S e t C o v e r

$\mathsf{Minimum-SetCover}$

(1 + \ln (n))

$(1+\ln(n))$

M i n i m u m - V e r t e x C o v e r

$\mathsf{Minimum-VertexCover}$

2

$2$

r_{A} (x) = \frac{1}{1 - ϵ_{A} (x)} ϵ_{A} (x) = 1 - \frac{1}{r_{A} (x)} .

$r_A(x)=\frac{1}{1-\epsilon_A(x)}\qquad \epsilon_A(x)=1-\frac{1}{r_A(x)}.$

$\epsilon<1/2$ $r<2$ $\epsilon\ge 1/2$ $r\ge 2$

$\alpha$ $\alpha\le 1$ $\alpha\ge 1$ $\alpha=1$

$O$ $NPO$ $r$ $r\ge1$

Już prawie koniec. Chcielibyśmy skopiować udane idee redukcji i kompletności z teorii złożoności. Obserwacja jest taka, że wiele trudnych do NP wariantów decyzyjnych problemów optymalizacyjnych można wzajemnie redukować, podczas gdy ich warianty optymalizacyjne mają różne właściwości dotyczące ich przybliżalności. Wynika to z wielomianowej redukcji Karp stosowanej w redukcjach kompletności NP, która nie zachowuje funkcji celu. I nawet jeśli funkcje celu zostaną zachowane, redukcja czasu Karp wielomianu może zmienić jakość rozwiązania.

$O_1$ $O_2$ $O_2$ $O_1$

$O_1=(X_1,L_1,f_1,opt_1)$ $O_2=(X_2,L_2,f_2,opt_2)$ $NPO$ $O_1$ $AP$ $O_2$ $O_1\le_{AP} O_2$ $g$ $h$ $c$

$g(x_1, r)\in X_2$ $x_1\in X_1$ $r>1$
$L_2(g(x, r_1))\ne\emptyset$ $L_1(x_1)\ne\emptyset$ $x_1\in X_1$ $r>1$
$h(x_1, y_2, r)\in L_1(x_1)$ $x_1\in X_1$ $r>1$ $y_2\in L_2(g(x_1,r))$
$r$ $g$ $h$
$f_{2} (g (x_{1}, r), y_{2}) \leq r \Rightarrow f_{1} (x_{1}, h (x_{1}, y_{2}, r)) \leq 1 + c \cdot (r - 1)$ $f_2(g(x_1,r),y_2)\le r \Rightarrow f_1(x_1,h(x_1,y_2,r))\le 1+c\cdot(r-1)$ $x_1\in X_1$ $r>1$ $y_2\in L_2(g(x_1,r))$

$g$ $h$ $r$ $g(x_1)$ $h(x_1, y_2)$

$O_2\in APX$ $O_1\le_{AP} O_2$ $O_1\in APX$

$\mathcal{C}$ $\mathcal{C}$

Pozwolić $O$ $NPO$ $\mathcal{C}$ $NPO$ $O$ $\mathcal{C}$ $\le_{AP}$ $O'\in\mathcal{C}$ $O'\le_{AP} O$

$\mathcal{C}$ $\mathcal{C}$ $\le_{AP}$ $\mathcal{C}$

$NPO$ $APX$ $NPO$ $\mathsf{SAT}$ $\mathsf{Weighted-Satisfiability}$ $NPO$ $\mathsf{Maximum-3SAT}$ $APX$

— uli
źródło

No i proszę przyjąć moje przeprosiny za ten stosunkowo długi post, ale nie miałem czasu na napisanie krótszego.

— uli

linia punktowa jest oczywiście taka, że według twierdzenia PCP można połączyć MAX3SAT i SAT, co pokazuje, że NP jest trudne do przybliżenia MAX 3SAT do lepszej niż jakaś stała. W pewnym sensie jest to odpowiednik twierdzenia Cooka-Levina.

— Suresh,

@Suresh Oczywiście, ale wspomniany wynik wymaga redukcji zachowującej odstępy, o ile pamiętam. A jak już pisałeś o nich w swoim poście, nie chciałem ich tutaj kopiować.

— uli

Świetna odpowiedź, +1! Zastanawiam się, czy twoja odpowiedź jest oparta na niektórych referencjach?

— Tim

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

— uli

Zazwyczaj pokazywana jest twardość NP „luki” wersji problemu. Załóżmy na przykład, że chcesz pokazać, że trudno jest zbliżyć wartość parametru SET COVER do współczynnika 2.

Zdefiniujesz następującą „obietnicę” wystąpienia SET COVER, którą nazwiemy 2-GAP-SET-COVER:

$\ell$

$\ell$
$2\ell$

Załóżmy, że pokazujemy, że problem decydowania o tym, w którym z dwóch przypadków występuje problem, jest NP-zupełny. Następnie wykazaliśmy, że przybliżenie SET COVER do współczynnika 2 jest trudne NP, ponieważ moglibyśmy użyć takiego algorytmu do rozróżnienia tych dwóch przypadków.

— Suresh
źródło

Dwie istniejące odpowiedzi są bardzo pouczające, ale nie sądzę, że żadna z nich tak naprawdę odpowiada na pytanie, które brzmi: „W jaki sposób problem, który nie jest nawet problemem decyzyjnym, może być trudny do rozwiązania, gdy NP jest klasą problemów decyzyjnych ?

$L$ $L$ $L$

Kilka przykładów.

$L$ $L$ $L$ $L$
#SAT to problem obliczania liczby spełniających przypisań formuł CNF. Wyraźnie nie ma go w NP, ponieważ, jak zauważyłeś, NP jest klasą problemów decyzyjnych, a #SAT nie jest jednym z nich. Jednak #SAT jest NP-trudny przy wielomianowych redukcjach Turinga, ponieważ możemy zredukować do niego SAT. Biorąc pod uwagę instancję SAT, pytamy, ile jest satysfakcjonujących zadań: jeśli jest co najmniej jeden, mówimy „zadowalający”; w przeciwnym razie „niezadowalający”.
$\varphi$ $\varphi$ $\varphi$ $\varphi'=\varphi \wedge (Z_1\vee \dots \vee Z_{10})$ $Z_i$ $\varphi'$ $\varphi$ $\varphi'$ $\varphi$ $\varphi'$

— David Richerby
źródło