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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.