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

25

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?

cc.complexity-theory complexity-classes padding

— Gabgoh
źródło

11

Chciałbym zauważyć, że nie wszystkie wyniki klas złożoności idą w górę. Na przykład, jeśli udowodniłeś , to oznaczałoby to . Ogólnie rzecz biorąc, zapadnięcia się zwiększają, a separacje maleją.

E X P \neq N E X P

$EXP \neq NEXP$

P \neq N P

$P \neq NP$

— Robin Kothari

w rzeczy samej. W rzeczywistości wydaje się to dobrym sposobem, aby o tym pomyśleć, ponieważ separacje są bardziej intuicyjne niż załamania.

— gabgoh

2

@Robin, @gabgoh: nawet niektóre upadki idą w dół, ale nie przez wypełnianie argumentów. Zobacz na przykład arxiv.org/abs/cs/9910008 .

— Joshua Grochow

30

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

— Russell Impagliazzo
źródło

14

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ę.

— Karolina Sołtys
źródło

13

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

Argument dopełniania działa z , komponując z deterministyczną wersją TM dla języka z niższej niedeterministycznej klasy. Wyjścia 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$

— András Salamon
źródło

5

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ść : $A\subseteq \Sigma^{ * }$ $x\in\Sigma^{ * }$

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

II. jeśli jest w ( ), to jest w ( ). $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 i z ). 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 . Otrzymujemy dane wejściowe długości , myślimy o tym jako dane wejściowe o długości : $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)$

— Kaveh
źródło

1

ten drugi argument, który widzę jako rodzaj argumentu „transformacja zmiennych”, przyszedł mi do głowy. Nie rozumiem jednak, dlaczego nie można po prostu „pomyśleć” o tym, że ma on wkład powiedzmy

co tłumaczy to w dół. Nie wydaje mi się, żeby to całkiem działało, chociaż dwa inne podejścia, myślenie o tym w kategoriach zapewnienia większej ilości zasobów algorytmowi NP, a także w kategoriach kompresji vs wypełniania ma sens.

N = l o g (n)

$N=log(n)$

— gabgoh

1

Trzeci sposób, aby o tym myśleć, to spojrzeć na rozmowę. Nie podążyłem za tym podejściem do gorzkiego końca, ale jeśli pojawi się jakaś świetna wiedza, opublikuję ją jako odpowiedź na siebie.

— gabgoh

1

@ gabgoh: To jest delikatniejsze niż zwykła zmiana zmiennych. Mam na myśli na wejściu jako o długości

, to działa bo

, po prostu wyobrazić, że istnieje wystarczająco dużo wykroje na koniec pierwotnego wejścia do uczynienia długości równej

, ale jak możesz myśleć o wprowadzeniu długości

jako długości

? Nie zapominaj, że w nawiasie znajduje się długość danych wejściowych! tzn. jest to część danych wejściowych, od której wyjście funkcji będzie zależeć.

N = 2^{n^{O (1)}}

$N=2^{n^{O(1)}}$

n \leq N

$n\leq N$

N

$N$

n

$n$

N = \log (n)

$N=\log(n)$

— Kaveh

1

[ciąg dalszy] Biorąc to pod uwagę, może to również pomóc: załóżmy, że dane wejściowe są jednoargumentowe i mają długość

, to możemy je skompresować do

bitów i faktycznie to by działało! Problem, jakim jest

(

) z kodowaniem jednoargumentowym, dotyczy

(

) z kodowaniem binarnym.

n

$n$

N = ⌈ \log (n) ⌉

$N = \lceil \log(n) \rceil$

P

$P$

N P

$NP$

E X P

$EXP$

N E X P

$NEXP$

— Kaveh

1

Wydaje mi się, że mam problem z frazą „myślenie o”, nie mogę owinąć głowy tym, co oznacza myśleć o mniejszym wkładzie jako większym wkładzie i co to w rzeczywistości robi. Zdaję sobie sprawę, że nie możesz myśleć o

, z tego powodu, który podajesz, co jest powtórzeniem argumentu wypełniania, a nie czystą analogią. W końcu, kiedy zmieniamy zmienne, zawsze myślimy o zmiennych w kategoriach innych zmiennych, ale w przeciwieństwie do zmiennych rzeczywistych jest to trochę „nieściśliwe”. Nie mówię, że to zła odpowiedź, ale osobiście mi to nie pomaga.

N = l o g (n)

$N=log(n)$

— gabgoh