Dlaczego problemy z uzupełnianiem NP nie mają podobnych współczynników aproksymacji?

Ponieważ 2 problemy NP-zupełne są z definicji redukowalne względem siebie, więc rozwiązanie jednego z nich można uzyskać za pomocą czarnej skrzynki rozwiązującej drugi, dlaczego nie mają podobnych współczynników aproksymacji (w odniesieniu do ich odpowiedników optymalizacyjnych )? Wydaje mi się, że pewne stałe lub nawet wielomianowe znoszenie może być zrozumiane, ale mamy przypadek algorytmów aproksymacji współczynnika stałego dla niektórych problemów NP-zupełnych, a z drugiej strony innych problemów, których nie da się aproksymować algorytmem aproksymacji współczynnika wielomianowego , takie jak ogólny TSP? Dziękuję Ci

cc.complexity-theory approximation-algorithms reductions N27
źródło

ponieważ redukcje czarnej skrzynki zachowują tylko aspekt TAK / NIE problemów (decyzji), a nie bliskość przybliżeń.

Suresh Venkat

jeśli zredukuję 3SAT do pokrycia wierzchołków, wówczas pokrycie wierzchołków o rozmiarze k oznacza satysfakcję i odwrotnie. Ale jeśli dostanę pokrycie wierzchołka o rozmiarze 2k, nie oznacza to, że mogę spełnić połowę klauzul.

Suresh Venkat

Wybierz konkretną redukcję z jednego problemu pełnego NP do drugiego i spróbuj go rozszerzyć, aby zachować proporcje przybliżenia. Zobaczysz, co idzie nie tak.

Peter Shor,

Odpowiedź Petera jest naprawdę najlepsza. Po prostu spróbuj i zobacz, co się stanie. Myślę, że przez filozoficzny sceptycyzm masz na myśli „tak naprawdę nie rozumiem intuicji”. Czasami najlepszym sposobem jest po prostu wypróbowanie kilku przykładów i zwiększenie intuicji.

Suresh Venkat

\log | C |

$\log |C|$

| C |

$|C|$

| C |^{2}

$|C|^2$

2^{| C |}

$2^{|C|}$

C

$C$

Jukka Suomela,

Odpowiedzi:

Redukcje są zdefiniowane w odniesieniu do wersji decyzji problemów. Współczynniki aproksymacji dla ich wersji optymalizacyjnych to osobne pytanie, które wydaje się powiązane, ale niekoniecznie musi być. Więc aby odpowiedzieć na twoje pytanie pytaniem, z filozoficznego punktu widzenia, dlaczego miałbyś oczekiwać, że klasowy NPC zachowa proporcje aproksymacji, jeśli nie zostaną one zdefiniowane w odniesieniu do nich w pierwszej kolejności?

Lew Reyzin
źródło

„Redukcje są definiowane w odniesieniu do wersji decyzji problemów”. Czy to prawda, powiedzmy, redukcje Levina ?

MS Dousti,

Masz rację, nie wszystkie redukcje są zdefiniowane jako wersje decyzyjne wrt, ale możemy zdefiniować NPC tylko w kategoriach redukcji czarnych skrzynek, a potem myślę, że może to prowadzić do debat na temat tego, jak te klasy zmieniają się z zastosowaną redukcją ... Powinienem powiedzieć: „NPC klasy jest zdefiniowany pod kątem problemów decyzyjnych”. Nie jest to tak naprawdę dokładny argument, ponieważ moglibyśmy nawet zdefiniować klasę problemów decyzyjnych, których wersje optymalizacyjne zachowują współczynniki aproksymacyjne, ale nie to robimy dla klasowego NPC. Wydaje mi się, że pytanie @ N27 jest filozoficznym zarzutem, wolno mi dać odpowiedź filozoficzną. :)

Lew Reyzin