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

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 ”.$P \neq NP$$NP \neq coNP$$A$$A$$\alpha$$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.$n$$NP = 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=coNP$$NP=coNP$$P \neq NP$

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 $NP \neq coNP$$NP$

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 $1-\varepsilon$$\varepsilon > 0$$1-\varepsilon$$1-\varepsilon$$1-\varepsilon$$coNP$$NP=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ć problem$NP \neq coNP$$P \neq NP$$NP$$NP$$BPP$$P \neq NP$nie 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ąć.$P \neq NP$$NP \neq coNP$$NP \neq coNP$$P \neq NP$

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.

P ≠ N P N P ≠ c o N P P ≠ N P P ≠ N P N P ≠ c o N $NP \ne coNP$ 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 .$P \ne NP$$NP\ne coNP$$P\ne NP$$P\ne NP$$NP\ne coNP$

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 $\prod_2^P$$NP \ne coNP$$NP$$\prod_2^P$

Noga Alon, Ograniczone kolorowanie wykresów