Nieuzasadniona moc niejednolitości

Z punktu widzenia zdrowego rozsądku łatwo jest uwierzyć, że dodanie niedeterminizmu do znacznie rozszerza jego moc, tj. jest znacznie większy niż . W końcu niedeterminizm umożliwia wykładniczy paralelizm, który niewątpliwie wydaje się bardzo silny. $\mathsf{P}$$\mathsf{NP}$$\mathsf{P}$

Z drugiej strony, jeśli po prostu dodamy niejednolitość do , uzyskując , wówczas intuicja jest mniej jasna (zakładając, że wykluczymy języki nierekurencyjne, które mogłyby wystąpić w ). Można się spodziewać, że samo dopuszczenie różnych algorytmów wielomianu czasu dla różnych długości wejściowych (ale nie opuszczenie sfery rekurencyjnej) jest mniej potężnym rozszerzeniem niż równoległość wykładnicza w niedeterminizmie.$\mathsf{P}$$\mathsf{P}/poly$$\mathsf{P}/poly$

Co ciekawe, jeśli porównamy te klasy z bardzo dużą klasą $\mathsf{NEXP}$ , wówczas zobaczymy następującą sprzeczną z intuicją sytuację. Wiemy, że $\mathsf{NEXP}$ właściwie zawiera $\mathsf{NP}$ , co nie jest zaskakujące. (W końcu $\mathsf{NEXP}$ pozwala na podwójnie wykładniczą równoległość.) Z drugiej strony, obecnie nie możemy wykluczyć $\mathsf{NEXP}\subseteq \mathsf{P}/poly$ .

Zatem w tym sensie niejednorodność po dodaniu do czasu wielomianowego prawdopodobnie czyni go niezwykle potężnym, potencjalnie silniejszym niż niedeterminizm. Może nawet posunąć się do symulacji podwójnie wykładniczej równoległości! Chociaż uważamy, że tak nie jest, ale fakt, że obecnie nie można tego wykluczyć, wciąż sugeruje, że teoretycy złożoności walczą tutaj z „potężnymi mocami”.

Jak wytłumaczysz inteligentnemu laikowi, co kryje się za tą „nieracjonalną mocą” niejednolitości?

Krótką odpowiedzią jest to, że nie jest to pierwsza rzecz w teorii złożoności, którą starałbym się wyjaśnić laikowi! Aby nawet docenić ideę niejednorodności i tego, w jaki sposób różni się ona od niedeterminizmu, musisz być w głębi chwastów z definicjami klas złożoności, niż wielu ludzi jest skłonnych zdobyć.

Powiedziawszy to, jedną z perspektyw, które uważałem za pomocne, tłumacząc P / poli studentom, jest to, że niejednorodność naprawdę oznacza, że ​​możesz mieć nieskończoną sekwencję coraz lepszych algorytmów, gdy przechodzisz do coraz większych długości wejściowych. W praktyce wiemy na przykład, że naiwny algorytm mnożenia macierzy działa najlepiej dla matryc o wielkości około 100 x 100, a następnie w pewnym momencie mnożenie Strassena staje się lepsze, a późniejsze algorytmy stają się lepsze tylko dla astronomicznie dużych matryc, które nigdy nie powstałyby w praktyce. A co, jeśli miałbyś magiczną umiejętność wyzerowania najlepszego algorytmu dla dowolnego zakresu n, z którym akurat pracowałeś?

Jasne, to byłaby dziwna umiejętność, a biorąc pod uwagę wszystkie kwestie, prawdopodobnie nie tak przydatna jak umiejętność rozwiązywania problemów NP-zupełnych w czasie wielomianowym. Ale ściśle mówiąc, byłaby to umiejętność nieporównywalna : nie jest to umiejętność, którą można uzyskać automatycznie, nawet jeśli P = NP. Rzeczywiście, możesz nawet skonstruować wymyślone przykłady problemów nieobliczalnych (np. Biorąc pod uwagę 0 ⁿ jako dane wejściowe, czy n- ^ta maszyna Turinga zatrzyma się?), Które ta zdolność pozwoli ci rozwiązać. To jest siła niejednorodności.

Aby zrozumieć sens rozważania tej dziwnej mocy, prawdopodobnie powinieneś coś powiedzieć o dążeniu do udowodnienia dolnych granic obwodu oraz o tym, że z punktu widzenia wielu naszych technik dolnych granic jednolitość wydaje się dziwna dodatkowy warunek, którego prawie nigdy nie potrzebujemy.

Oto argument „gładkości”, który niedawno usłyszałem w obronie twierdzenia, że ​​niejednolite modele obliczeń powinny być silniejsze, niż się spodziewamy. Z jednej strony wiemy z twierdzenia hierarchii czasu, że istnieją funkcje obliczalne w czasie , które nie są obliczalne na przykład w czasie O ( 2 n ) . Z drugiej strony, zgodnie z twierdzeniem Lupanova, każda funkcja boolowska na n wejściach jest obliczalna przez obwód wielkości ( 1 + o ( 1 ) ) 2 n /$O(2^{2n})$$O(2^{n})$$n$$(1+o(1))2^n/n$. Jeśli więc twierdzimy, że niezgodność nie daje dużej mocy, to znaczy, że powinien zachowywać się jak D T I M E ( f ( n ) O ( 1 ) ) , to twierdzenie to powinno nagle przestać przytrzymanie, gdy f ( n ) staje się 2 O ( n ) . Ale to zachowanie - dwie miary złożoności idą w parze, aż nagle jedna z nich staje się wszechmocna - wydaje się arbitralna i nieco nienaturalna.$\mathsf{SIZE}(f(n))$$\mathsf{DTIME}(f(n)^{O(1)})$$f(n)$$2^{O(n)}$

Z drugiej strony, jeśli obwody są na tyle silne, że , to według Karp-Lipton hierarchia wielomianowa zapada się na drugi poziom, co również byłoby dziwne: dlaczego kwantyfikatory nagle przestałyby dawać obliczeniom większą moc ? Nie jestem pewien, gdzie nas to zostawia.$\mathsf{NP} \subseteq \mathsf{P/poly}$

Zakładać, że rozmawiać z osobą, o i N P oznacza, że osoba zna P vs N P pytaniem i dualnością weryfikacji rozwiązywania.$\mathbb{P/poly}$$\mathbb{NP}$$\mathbb{P}$$\mathbb{NP}$

Następnie postaram się wyjaśnić, że jest tak potężny, ponieważ dla każdej innej długości TM otrzymuje poradę, której może całkowicie zaufać. Następnie wspomniałbym, że możemy opracować twarde (właściwie nie do obliczenia TM) języki, które mają 1 słowo na długość wejściową (tj. Jednoargumentową), więc są w P / poly! Ale może wielomianowa długa rada nie wystarczy, aby rozwiązać wszystkie języki w N P , ponieważ mamy tam inną wskazówkę dla każdego innego wejścia.$\mathbb{P/poly}$$\mathbb{NP}$

Z drugiej strony, chciałbym przypomnieć, że osoby, które musi zweryfikować odpowiedź, nie ufa go całkowicie. Dlatego nie możemy zastosować tej samej porady dla każdej długości wejściowej, może nie być możliwa do zweryfikowania!$\mathbb{NP}$

$\mathbb{NP}$$\mathbb{P/poly}$

Krytycznym punktem dla dobrego zrozumienia, które moim zdaniem jest również powszechne podczas nauczania tego przedmiotu po raz pierwszy, jest wyjaśnienie, że porady i „wskazówki” (tj. Certyfikat) to różne rzeczy i jak się różnią.

Dla mnie najostrzejszą ilustracją siły niejednorodności jest to, że odpowiednio wyściełana wersja problemu zatrzymania jest już w P / 1. Wystarczy jeden kawałek porady, aby wybrać ten język za pomocą trywialnej bazy TM, która po prostu zwraca fragment porady.

Oczywiście, wypełnienie niezdecydowanego języka wykładniczą kwotą oznacza, że ​​nie jest on „moralnie” w P / poli. Ale to pokazuje, że należy zachować ostrożność, dopuszczając niejednorodność.

I have the impression that the real issue here is the unreasonable heavy burden of proof, not the unreasonable power of non-uniformity. As the answers by chazisop and András Salamon already stress, undecidable languages become computable even in very restricted non-uniform languages, because the burden of proof has been completely waived.

The basic intuition why we might get away without a proof is that there are only $2^n$ different inputs of length $n$, for which we have to check that the circuit gives the correct answer. So it seems like there would be a proof of at most exponential length in $n$, that the circuit indeed gives the correct answer. But this is only true as long as there exists for each input of length $n$ a proof of at most exponential length in $n$, that the input is (not) contained in the language (if it is actually (not) contained in the language). Note that exponentially many inputs times an at most exponentially long proof for each input gives a complete proof for all inputs of exponential length, because $2^n\exp(O(n))=\exp(n\log(2)+O(n))=\exp(O(n))$.

If we require the existence of a proof of at most exponential length in $n$ for non-uniform languages, then we can prove that all these languages are contained in $\mathsf{NEXP}$. The corresponding non-deterministic algorithm just needs a hint that contains both a "small" circuit together with a "small" proof that this circuit really computes what it is supposed to compute.

The same non-deterministic algorithm would also show $\mathsf{P/poly'}\subseteq \mathsf{NP}$, if we required instead the existence of proofs of at most polynomial length in $n$ that the circuit is suitable. Notice that this restricted $\mathsf{P/poly'}$ could still be more powerful than $\mathsf{P}$. Even Karp-Lipton (i.e. that the polynomial hierarchy collapses if $\mathsf{NP}\subseteq\mathsf{P/poly'}$) still holds true, but this statement is less interesting than the real Karp-Lipton theorem.