Czy APX jest zawarty w NP?

15

Mówi się, że problem P występuje w APX, jeśli istnieje pewna stała c> 0, tak że istnieje algorytm aproksymacji czasu wielomianowego dla P ze współczynnikiem aproksymacji 1 + c.

APX zawiera PTAS (widoczne po prostu przez wybranie dowolnej stałej c> 0) i P.

Czy APX jest w NP? W szczególności, czy istnienie algorytmu aproksymacji czasu wielomianowego dla jakiegoś współczynnika aproksymacji sugeruje, że problem dotyczy NP?

cc.complexity-theory complexity-classes apx Andrew W.
źródło
Myślę, że „to, co wiadomo o klasie X w stosunku do wszystkich innych klas Y”, jest zdecydowanie zbyt niejasne jako pytanie, chyba że podano dalsze szczegóły na temat poszukiwanych rodzajów relacji.
András Salamon,
Mam na myśli relacje takie jak „zawiera”, „zawiera się w”, „nie zawiera”.
Andrew W.,
Po namyśle zawęziłem pytanie do konkretnego związku, który mnie najbardziej interesuje.
Andrew W.,
1
Co dokładnie oznacza pytanie, czy APX jest zawarty w NP? APX składa się z problemów związanych z optymalizacją NP, podczas gdy NP składa się z problemów decyzyjnych. Ponadto z definicji wersja decyzyjna problemu optymalizacji NP znajduje się w NP. Może miałeś na myśli coś innego?
Joshua Grochow
Masz rację, Joshua. Ian odpowiedział na pytanie, które powinienem zadać.
Andrew W.,

Odpowiedzi:

20

APX jest zdefiniowany jako podzbiór NPO, więc tak, jeśli problem optymalizacji dotyczy APX, to odpowiedni problem decyzyjny jest w NP.

Jednakże, jeśli pytasz, czy arbitralny problem musi dotyczyć NP (lub NPO), jeśli występuje przybliżenie O (1) w czasie wielokrotnym, odpowiedź brzmi nie. Nie znam żadnych naturalnych problemów, które mogłyby służyć jako kontrprzykład, ale można zdefiniować problem sztucznej maksymalizacji, w którym celem jest suma dwóch terminów, dużego terminu, który można łatwo zoptymalizować w P, i znacznie mniejszego terminu to dodaje niewielką ilość, jeśli część rozwiązania koduje odpowiedź na jakiś trudny problem (poza NP). Następnie można znaleźć, powiedzmy, przybliżenie 2-czasowe w czasie wielocyfrowym, koncentrując się na łatwym terminie, ale znalezienie optymalnego rozwiązania wymagałoby rozwiązania trudnego problemu.

Ian
źródło
2
Zaakceptowałem twoją odpowiedź, ponieważ dotyczyła zarówno pytania, które zadałem („Czy APX jest zawarty w NP?”), Jak i pytania, które powinienem zadać („Czy czas O (1) w czasie wielokrotnym sugeruje dokładne rozwiązanie w NP?”).
Andrew W.,
1
Szeroką klasą problemów, które nie są zawarte w NPO i NP, ale których przybliżenie o stałym współczynniku jest klasa problemów online (pytanie o to, jaka klasa złożoności zawiera problemy online, znajduje się tutaj cstheory.stackexchange.com/questions/1664/... ) .
Oleksandr Bondarenko