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 ”.
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.
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 .
approximation-hardness
conditional-results
Shiva Kintali
źródło
źródło
Odpowiedzi:
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 PNP≠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 P1−ε ε>0 1−ε 1−ε 1−ε 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ć problemNP≠coNP P≠NP NP NP BPP P≠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≠NP NP≠coNP NP≠coNP P≠NP
źródło
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.
źródło
P ≠ N P N P ≠ c o N P P ≠ N P P ≠ N P N P ≠ c o N PNP≠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≠NP NP≠coNP P≠NP P≠NP NP≠coNP
źródło
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 2∏P2 NP≠coNP NP ∏P2
Noga Alon, Ograniczone kolorowanie wykresów
źródło