Dlaczego równości między klasami złożoności przekładają się w górę, a nie w dół?

Cześć chłopaki, rozumiem, że sztuczka dopełniania pozwala nam tłumaczyć klasy złożoności w górę - na przykład . Wypełnianie polega na „nadmuchiwaniu” danych wejściowych, uruchamianiu konwersji (powiedzmy od powiedzmy na ), co daje „magiczny” algorytm, który można uruchomić na wypełnionym wejściu. Chociaż ma to sens techniczny, nie mogę zrozumieć, jak to działa. Co tu się właściwie dzieje? Czy istnieje prosta analogia do tego, co to jest wypełnienie?$P=NP \rightarrow EXP=NEXP$$NP$$P$

Czy można podać rozsądny powód, dla którego tak jest?

Myślę, że najlepszym sposobem na uzyskanie intuicji w tej kwestii jest zastanowienie się, jakie są kompletne problemy wykładniczych klas czasowych. Na przykład, kompletnymi problemami dla NE są standardowe problemy z kompletnym NP na zwięźle opisywalnych danych wejściowych, np. Biorąc pod uwagę obwód opisujący macierz przyległości wykresu, czy wykres 3 jest barwny? Następnie problem tego, czy E = NE staje się równoważny z tym, czy problemy NP można rozwiązać w czasie wielomianowym na zwięźle opisywalnych danych wejściowych, np. Te o małej skutecznej złożoności Kołmogorowa. Nie jest to oczywiście mocniejsze niż to, czy można je rozwiązać na wszystkich wejściach. Im większa granica czasowa, tym mniejsza złożoność Kołmogorowa odpowiednich danych wejściowych, więc w przypadku większych granic czasowych zawijają się algorytmy, które działają na mniejszych podzbiorach danych wejściowych.

Russell Impagliazzo

OK, więc Twoim celem jest pokazanie, że oparciu o (nie nie określają, czym dokładnie są te klasy, po prostu wiemy, że są one sparametryzowane wielkością wejściową). Mamy język , decyduje pewnego algorytmu . Teraz tworzymy język , wpisując każde słowo w$CLASS_1[g(f(n))] = CLASS_2[h(f(n))]$$CLASS_1[g(n)] = CLASS_2[h(n)]$$L \in CLASS_1[g(f(n))]$$A$$L'$ , tak aby jego długośćteraz, i widzimy, że jest on zawarty w(nasz nowy algorytmzasadzie tylko ignoruje dodane zera i uruchamiana rzeczywistym krótkim wejściu).$x \in L$$f(n)$$CLASS_1[g(n)]$$A'$$A$

Robimy to: pobieramy język z większej klasy i uzupełniamy go, aby można go było rozwiązać za pomocą słabszego algorytmu zapewniającego kontrolę w mniejszej klasie - słabszy algorytm może to zrobić, ponieważ ma taką samą ilość „prawdziwa praca” do zrobienia jak poprzednio, ale ma swoje ograniczenia (będące funkcją długości wejściowej) zniesione przez rozszerzenie wejściowej.

Teraz wiemy, że a zatem (decyduje jakiś algorytm ). Chcielibyśmy dostać się stąd do . Ale to jest proste - algorytm decydujący po prostu odpowiednio dopełnia wejście i uruchamia na dopełnionym wejściu.$L' \in CLASS_1[g(n)]$$L' \in CLASS_2[h(n)]$$B'$$L \in CLASS_2[h(f(n))]$$B$$L$$B'$

Ten krok można podsumować następująco: chcemy zdecydować w większej, bardziej zasobnej klasie. Korzystając z naszych dodatkowych zasobów, wypełniamy dane wejściowe i uruchamiamy algorytm decydujący o wypełnionym języku$L$ .

Oczywiście są tu pewne szczegóły techniczne (np. Musimy upewnić się, że wypełnienie można wdrożyć w rozważanych przez nas klasach), ale po prostu je ignoruję, aby dać ogólną intuicję.

Widzę argumenty dopełniające pod względem zwartości reprezentacji. Pomyśl o dwóch maszynach tłumaczących Turinga: wysadza instancje, a C ponownie je kompresuje.$B$$C$

Argument dopełniania działa z , komponując B z deterministyczną wersją TM dla języka z niższej niedeterministycznej klasy. Wyjścia B wspólnie tworzą język, który nie jest zwięźle reprezentowany, więc staje się to „łatwiejsze”.$B$$B$$B$

Nie można zastosować tej idei w inny sposób, używając , ponieważ tylko niektóre języki w klasie łatwej są generowane przez wysadzenie języków w klasie trudnej.$C$

Aby uczynić go bardziej intuicyjnym, spójrzmy na to, co dzieje się bardziej abstrakcyjnie!

Mamy dwie transformacje, jeden dla wejścia i jedno dla problems.I oznaczać będzie zarówno z nich przez , to będzie jasne z kontekstu, kiedy to pierwszy z nich, a kiedy jest drugi.$pad$

Te dwie transformacje mają następującą właściwość:

I. dla wszystkich problemów , dla wszystkich wejść x ∈ Σ ∗ :$A\subseteq \Sigma^{ * }$$x\in\Sigma^{ * }$

iff x ∈ A ,$pad(x) \in pad(A)$$x \in A$

II. jeśli jest w E X P ( N E X P ), to p a d ( A ) jest w P ( N P ).$A$$EXP$$NEXP$$pad(A)$$P$$NP$

III. transformacja dla danych wejściowych jest w klasie złożoności ,$EXP$

Oczywiste jest, że przekształcenia dla wypełnienia mają te właściwości.

Teraz powód, że nie wiemy, jak to zrobić to samo w odwrotnym kierunku jest to, że nie mamy takich przekształceń wyściółką w odwrotnym kierunku (kiedy wymieniamy z P i N E X P z N P ). Pytanie brzmi dlaczego?$EXP$$P$$NEXP$$NP$

Nie mam formalnego argumentu, dlaczego nie ma obecnie takich przekształceń, ale intuicyjnie to, co powiedział András Salamon, jest poprawne. Łatwo jest zwiększyć rozmiar danych wejściowych, ale nie jest jasne, jak można je skompresować?

Innym sposobem na zrozumienie tego jest myślenie w następujący sposób. Załóżmy, że , i chcemy rozwiązać problem N E X P = N T i m e ( 2 n O ( 1 ) ) . Otrzymujemy dane wejściowe x długości n , myślimy o tym jako dane wejściowe o długości N = 2 n O ( 1 ) :$P=NP$$NEXP=NTime(2^{n^{O(1)}})$$x$$n$$N=2^{n^{O(1)}}$

$NEXP(n) = NTime(2^{n^{O(1)}}) = NTime(N) \subseteq NP(N) \subseteq P(N) = Time(N^{O(1)}) = Time(2^{n^{O(1)}}) = EXP(n)$