Konsekwencje kompletnych problemów dla NP przecina CoNP

Jakie są konsekwencje posiadania kompletnych problemów w $NP\cap coNP$ ?

Jest to (szeroko) otwarty problem; jak w środku, prawie nic nie wiemy. W szczególności, ze względu na podstępność w udowadnianiu $NP \cap coNP$ 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 $NP \cap coNP$ kompletnych problemów i dodajcie moje przemyślenia:

Obecnie mamy tylko „słabych”, naturalnych kandydatów do członkostwa w $NP \cap coNP - P$ 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 $\le k$ , ma losową złożoność czasową $poly(n) 2^{\sqrt{k log(k)}}$ . (Jeśli w$NP \cap coNP - P$wystę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 $NP \cap coNP = 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 jak$PSPACE$ i#$P$ .

Jednak trudność w zapewnieniu podobnej reprezentacji dla $NP \cap coNP$ 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 $NP \cap coNP$ pomocą dwóch niedeterministycznych maszyn Turinga, które rzekomo rozpoznają języki komplementarne:

Pytanie: Czy maszyna Turinga $M^*$ zatrzymuje się na wejściu $x \in {0,1}^n$ ?

Skonstruuj dwie liniowe maszyny Turinga $M_1$ i $M_2$ w następujący sposób. Na wejściowego $y$ , $M_1$ odczytuje dane i zawsze przyjmuje. $M_2$ zawsze odrzuca, chyba że $|y| \ge |x|$a $M^*$ przyjmuje $x$ w krokach $\le |y|$.

Dlatego $M_1$ i $M_2$ 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 $NP \cap coNP$ nie jest rozpoznawalna w czasie wielomianowym. Pozostaje pytanie: w jaki sposób reprezentujesz problemy $NP \cap coNP$ , 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 $NP \cap coNP$ . Dlatego twierdzę, że istnienie techniki dowodowej, która może rozwiązać kompletność $NP \cap coNP$ będzie tutaj większą historią - nie zaś „automatycznymi” wynikami $NP \cap coNP$ 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).