Konsekwencje kompletnych problemów dla NP przecina CoNP

24

Jakie są konsekwencje posiadania kompletnych problemów w NPcoNP ?

Marcos Villagra
źródło
Zobacz także mathoverflow.net/questions/34889/…
Jukka Suomela
Znam ten link. Moje pytanie dotyczy konsekwencji. Na przykład, jeśli język L jest kompletny dla wówczas PH spada do i-tego poziomu lub coś w tym rodzaju. NPcoNPi
Marcos Villagra,
Właściwie zadałem to samo pytanie co komentarz w tym linku, ale chciałem, aby było to prawdziwe pytanie.
Marcos Villagra,
2
Tak, wiem, że wiesz, ale strona mathoverflow zawiera przydatne informacje dla innych.
Jukka Suomela,

Odpowiedzi:

18

Jest to (szeroko) otwarty problem; jak w środku, prawie nic nie wiemy. W szczególności, ze względu na podstępność w udowadnianiu NPcoNP kompletnych problemów, potrzebujemy bardzo różnych technik dowodowych niż obecnie. Dyskusja o konsekwencjach powinna jako taka zawierać tangens na temat „Co oznaczałoby posiadanie tak potężnych, nowych technik dowodowych?”.

W przypadku stosunkowo niedawnej dyskusji na ten temat znajduje się 26. kolumna Davida Johnsona dotycząca kompletności NP w Transakcjach ACM na algorytmach od 2007 r. ( PDF ). Pozwólcie mi sparafrazować niektóre wypowiedzi Dawida dotyczące kwestii udowodnienia istnienia NPcoNP kompletnych problemów i dodajcie moje przemyślenia:

Obecnie mamy tylko „słabych”, naturalnych kandydatów do członkostwa w NPcoNPP w tym sensie, że najsilniejszym dowodem ich członkostwa jest to, że nie udało nam się znaleźć dla nich algorytmu wielomianowego czasu. Wymienia kilku kandydatów: SMALL FACTOR, SIMPLE STOCHASTIC GAME i MEAN PAYOFF GAME. Niektóre z dodatkowej „dziwności” tych problemów wynikają z najlepszych heurystycznych czasów pracy w celu ich rozwiązania, np. MAŁY FACTOR, czyli INTEGER FACTOR k , ma losową złożoność czasową poly(n)2klog(k) . (Jeśli wNPcoNPPwystępują całkowite problemy, toczy taki sub-wykładniczy(ani czysto wykładniczy, ani całkowicie wielomianowy)środowisko uruchomieniowe jest endemiczne dla klasy?)

Tak konkretnie, chcielibyśmy, aby udowodnić coś takiego: A jest problemem tylko w P wtw NPcoNP=P , czyli kompletności wyniku podobnego twierdzenia Cook dla 3SAT i NP . Dla NP takie dowody powszechnie obejmować redukcję wielomian czasu (i naprawić swoje ulubione, dodatkowe ograniczenia, np Stoły redukcje, Karpa-redukcje). W rezultacie, zgodnie z technikami redukcji czasu wielomianowego, musi istnieć przypadek rozpoznawalnej reprezentacji klasy w czasie wielomianowym. W przypadku NP możemy użyć niedeterministycznych maszyn Turinga, które zatrzymują się w obrębie wielomianu, p(|x|) , liczba kroków. David zwraca uwagę, mamy podobne reprezentacje innych klas (gdzie status jest bardziej jasne), takich jakPSPACE i#P .

Jednak trudność w zapewnieniu podobnej reprezentacji dla NPcoNP polega na tym, że „naturalny” analog pozwala nam osadzić problem zatrzymania w reprezentacji, a zatem jest nierozstrzygalny . To znaczy rozważ następującą próbę przedstawienia NPcoNP pomocą dwóch niedeterministycznych maszyn Turinga, które rzekomo rozpoznają języki komplementarne:

Pytanie: Czy maszyna Turinga M zatrzymuje się na wejściu x0,1n ?

Skonstruuj dwie liniowe maszyny Turinga M1 i M2 w następujący sposób. Na wejściowego y , M1 odczytuje dane i zawsze przyjmuje. M2 zawsze odrzuca, chyba że |y||x|a M przyjmuje x w krokach |y|.

Dlatego M1 i M2 akceptują języki komplementarne iff M nie zatrzymuje się na wejściu x . Dlatego, sprzecznie, decyzja, czy dwie maszyny Turinga w czasie wielomianowym akceptują języki komplementarne, jest nierozstrzygalna.

Zatem „naturalna” reprezentacja problemów NPcoNP nie jest rozpoznawalna w czasie wielomianowym. Pozostaje pytanie: w jaki sposób reprezentujesz problemy NPcoNP , tak że można je rozpoznać po czasie wielomianowym?

Nie było znaczące prace na ten temat, ale jej sukces rozdzielczość to konieczne do udowodnienia kompletności w NPcoNP . Dlatego twierdzę, że istnienie techniki dowodowej, która może rozwiązać kompletność NPcoNP będzie tutaj większą historią - nie zaś „automatycznymi” wynikami NPcoNP problemów kompletnych ( np. klasy złożoności, być może upadające), o których wiemy już (a raczej będziemy świadomi , hipotetycznie w przyszłości).

Daniel Apon
źródło
1
dzięki za plik PDF. Jeszcze go nie przeczytałem, ale zrobię to. Jest ten artykuł: „O funkcjach całkowitych, twierdzeniach o istnieniu i złożoności obliczeniowej”. Nimrod Megiddo i Christos Papadimitriou. Theoretical Computer Science 81, 1991. Nie chodzi o , ale o związaną z nim klasę funkcji TFNP, tj. T F N P = F ( N P c o N P ) . Istnieje następujące twierdzenie: „Występuje problem z pełnym FNP w TFNP iff NP = coNP”. Biorąc pod uwagę, że wyszukiwanie i decyzyjne problemy wielomianowo związane, czy twierdzenie to rozciąga się również na N PNPcoNPTFNP=F(NPcoNP)NPcoNP
To nie tłumaczy bezpośrednio (w sposób, który według mnie sugerujesz). Zauważ, że twierdzenie to nie dotyczy tylko KAŻDEGO pełnego problemu, ale problemu pełnego FNP. Jest to równoważne z powiedzeniem: „Istnieje NP-całkowity problem w NP \ cap coNP iff NP = coNP”. O ile mi wiadomo, możliwe jest, że NP \ cap coNP ma kompletne problemy, które różnią się od NP-kompletnych problemów, bez załamania PH . (Link jest dla zabawy;))
Daniel Apon
Uwaga: Nadal uważa się za mało prawdopodobne, aby sytuacja, którą opisałem powyżej jako możliwy, miała miejsce z tych samych powodów w odpowiedzi.
Daniel Apon,