Twardość aproksymacji przy założeniu NP! = CoNP

32

Dwa typowe założenia potwierdzające twardość wyników aproksymacji to i Unique Games Conjecture. Czy jest jakaś twardość wyników aproksymacji przy założeniu, że ? Szukam problemu takiego, że „trudno jest zbliżyć do współczynnika chyba że ”.PNPNPcoNPAAαNP=coNP

Wiadomym jest, że „pokazuje współczynnik NP twardość najkrótszym problemu wektora będzie oznaczać, że ”. Zauważ, że jest to „przeciwieństwo” tego, czego szukam.nNP=coNP

Wyjaśnienie: Możliwe jest, że i nadal pytanie P vs NP jest otwarte. Szukam twardości wyniku aproksymacji, który stanie się fałszem, jeśli ale pozostanie niezmieniony (tj. Nadal pozostaje przypuszczeniem) przez .NP=coNPNP=coNPPNP

Shiva Kintali
źródło
@ Kintali, wynik SVP jest interesujący. Czy znasz inne przykłady podobne do najkrótszego wyniku problemu wektorowego?
Mohammad Al-Turkistany
Nie znam więcej takich wyników.
Shiva Kintali

Odpowiedzi:

20

Oto prosta obserwacja. Jeśli założymy, że , to dość łatwo zauważyć, że istnieją problemy z optymalizacją , które w pewnym sensie nie mają nawet dobrych niedeterministycznych algorytmów aproksymacyjnych.N PNPcoNPNP

Na przykład twierdzenie PCP mówi, że można przełożyć SAT na problem rozróżnienia, czy klauzul jest spełniony i wszystkie klauzule są spełnione, dla niektórych . Załóżmy, że istnieje algorytm niedeterministyczny, który potrafi rozróżnić te dwa przypadki, w tym sensie, że algorytm niedeterministyczny może zgłaszać w każdej ścieżce obliczeniowej „wszystkie spełnione” lub „co najwyżej ” i mówi „co najwyżej ”na jakiejś ścieżce, jeśli najwyżej może być spełniony, w przeciwnym razie na każdej ścieżce obliczeniowej jest napisane„ wszystko spełnione ”, jeśli wszystkie równania mogą być spełnione. To wystarczy, aby zdecydować SAT w ,ε > 0 1 - ε 1 - ε 1 - ε c o N P N P = c o N P P = N P1εε>01ε1ε1εcoNPNP=coNP. Wydaje się jasne, że istnienie takiego niedeterministycznego algorytmu nie ma wpływu na to, czy .P=NP

Jest całkiem prawdopodobne, że istnieje bardziej „naturalny” scenariusz: problem optymalizacji, który jest trudny do oszacowania w deterministycznym wielomianowym czasie w ale nie jest znany jako trudny w . (Jest to prawdopodobnie to, o co naprawdę chciałeś zapytać.) Najpierw udowodniono wiele twardości wyników aproksymacji przy pewnym mocniejszym założeniu (np. nie w czasie podwykonawczym lub nie w ). W niektórych przypadkach późniejsze ulepszenia osłabiają niezbędne założenie, czasem nawet do . Mamy więc nadzieję, że odpowiedź na twoje pytanie jest nieco bardziej zadowalająca niż to. Trudno się zastanawiać, jak może istnieć problemNPcoNPPNPNPNPBPPPNPnie można udowodnić, że jest trudny do aproksymacji w deterministycznej polityce czasowej pod , ale można to udowodnić jako trudne pod . Oznaczałoby to, że mówi nam coś o obliczeniach deterministycznych, o których nie mówi; intuicyjnie trudno to pojąć.PNPNPcoNPNPcoNPPNP

Ryan Williams
źródło
Tak. Trudno pojąć, że takie wyniki twardości są nawet możliwe. Zastanawiałem się, czy możemy udowodnić brak takich wyników twardości. Uff ... komplikuje się.
Shiva Kintali,
(1) Obawiam się, że piszesz przypadek „tak” i „nie” w drugim akapicie. Łatwo jest zbudować niedeterministyczny algorytm, który robi to, co powiedziałeś (zgłasza „wszystko spełnione” w co najmniej jednej ścieżce, jeśli formuła jest zadowalająca i zgłasza „najwyżej 1 ε” we wszystkich ścieżkach, jeśli formuła jest daleka od zadowalającej ), po prostu testując wszystkie przypisania prawdy niedeterministycznie. (2) Zgadzam się z częścią „trudną do uchwycenia”.
Tsuyoshi Ito,
8

Zastrzeżenie: to nie jest bezpośrednia odpowiedź.

W rzeczywistości istnieje wiele innych warunków twardości innych niż P! = NP i UGC. David Johnson napisał piękną kolumnę do Transakcji na algorytmach w 2006 roku na ten właśnie temat. Wymienia wiele różnych założeń służących do wykazania twardości oraz ich wzajemne relacje.

Niestety są to wszystkie klasy NP vs deterministyczne (z wyjątkiem NP i co-AM). NP vs co-NP w ogóle nie jest objęty.

Suresh Venkat
źródło
2
Co ciekawe, David Johnson DOES rozmawia o NP vs co-NP w następnej kolumnie - NP-kolumna kompletności numer 26 !
Daniel Apon,
ah oczywiście. Powinienem był pamiętać. Ale bez przybliżeń ...
Suresh Venkat,
4

P N P N P c o N P P N P P N P N P c o N PNPcoNP jest silniejszą hipotezą niż ponieważ implikuje . Zatem każda twardość wyniku aproksymacji przy założeniu, że wynikałaby również z założenia .PNPNPcoNPPNPPNPNPcoNP

Mohammad Al-Turkistany
źródło
3
Możliwe jest, że NP = coNP i wciąż pytanie P vs NP jest otwarte. Szukam twardości wyniku aproksymacji, który stanie się fałszem, jeśli NP = coNP, ale pozostanie niezmieniony (tj. Nadal pozostanie przypuszczeniem) przez P! = NP.
Shiva Kintali,
W swoim pytaniu szukasz problemu A takiego, że „łatwo jest aproksymować w obrębie czynnika oznacza NP = coNP”, co jest równoważne z „Jeśli , to trudno jest aproksymować A w obrębie czynnika „. Edytuj swoje pytanie, aby odzwierciedlić swój komentarz. α N P c o N P αAαNPcoNPα
Mohammad Al-Turkistany
0

To nie jest bezpośrednia odpowiedź

k-Problem z wybieralnością jest . Przy założeniu, że , k-Choosability jest ściśle trudniejszy niż k-Coloring na ogólnych wykresach. Dlatego przybliżona liczba chromatyczna listy jest ściśle trudniejsza niż liczba chromatyczna. Wiadomo, że barwienie k jest trywialne dla grafów dwustronnych. Jednak określenie liczby chromatycznej grafów dwustronnych jest twarde. (nawet 3-wybór jest ) N P c o N P N P P 22PNPcoNPNP2P

Noga Alon, Ograniczone kolorowanie wykresów

Mohammad Al-Turkistany
źródło