Nieuzasadniona moc niejednolitości

33

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

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.PP/polyP/poly

Co ciekawe, jeśli porównamy te klasy z bardzo dużą klasą NEXP , wówczas zobaczymy następującą sprzeczną z intuicją sytuację. Wiemy, że N.miXP. właściwie zawiera N.P. , co nie jest zaskakujące. (W końcu N.miXP. pozwala na podwójnie wykładniczą równoległość.) Z drugiej strony, obecnie nie możemy wykluczyć N.miXP.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?

Andras Farago
źródło
16
Trudność w zrozumieniu niejednorodności (i udowodnienie dolnych granic obwodu ogólnego) niekoniecznie oznacza, że ​​niejednorodność jest potężna (w tym sensie, że można jej użyć do rozwiązania interesujących problemów).
Kaveh
4
Nie sądzę, żeby ktokolwiek wierzył a nawet N PP / p o l y . Fakt, że pytania te pozostają otwarte, jest bardziej stwierdzeniem o naszej żenującej niezdolności do udowodnienia dolnych granic obwodu. N.miXP.P./polyN.P.P./poly
Thomas
8
@Thomas: Nie będę zakładać, aby mówić do kogoś innego, ale powiem, że znam co najmniej jedną bardzo ceniony badacz, który rzeczywiście przypuszczenia, że . EXPP/poly
Joshua Grochow
2
@Thomas: Nie do końca, ale myślę, że chodzi o to, jak mało rozumiemy niejednorodność. Na przykład, dla wszystkich, co wiemy (i jak przypuszcza Kolmogorov, patrz cstheory.stackexchange.com/a/22048/129 ) P ma ckts wielkości . Jako inny przykład, wydaje się, że jest mało (jeśli w ogóle) naturalnych problemów znane są w P / P O l y , które nie są rzadkie ani BPP ( cstheory.stackexchange.com/questions/1662/... ). A jednak, biorąc pod uwagę ckts, można by pomyśleć, że P / p o l y jest znacznie silniejszy niż randomizacja + wyszukiwanie w tabeli. O(n)P/polyP/poly
Joshua Grochow
6
Echo @ thomas, jeśli nie możemy udowodnić, że NEXP nie jest w P / poly oznacza, że ​​istnieje „nieuzasadniona moc niejednorodności”, ponieważ ponieważ nie możemy udowodnić, że P <> NP oznacza, że ​​musi istnieć „nieracjonalna moc wydajnego obliczenia”.
Lance Fortnow

Odpowiedzi:

33

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

Scott Aaronson
źródło
2
Naprawdę podoba mi się argument „nieskończona sekwencja coraz lepszych algorytmów”. Tak naprawdę szukałem takich argumentów, które pomogą wyjaśnić studentom duży obraz. W jaki sposób ten argument stosuje się jednak, jeżeli otrzymuje z B P P ? Dla B P P samo oryginalne pytanie może być przekształcone, ponieważ obecnie nie możemy oddzielić N E X P od B P P albo. P/polyBPPBPPNEXPBPP
Andras Farago
7
BPP jest znacznie łatwiej motywować! To tylko próba modelowania siły randomizacji, która (w przeciwieństwie do niejednorodności) jest czymś, co jest używane przez cały czas w praktyce. (Nawiasem mówiąc, zapomniałem wspomnieć: innym sposobem motywowania niejednorodności byłoby zastosowanie kryptografii. Można zauważyć, że przeciwnicy mają luksus optymalizacji wszystkich swoich zasobów ataku w kierunku dowolnej długości klucza wybranej jako standard, więc ty powinienem mieć kryptosystem, który Twoim zdaniem jest bezpieczny przed niejednolitymi atakującymi na tej ustalonej długości, a nie tylko przed atakami mundurowymi.)
Scott Aaronson
1
W pełni zgadzam się, że motywacja jest łatwiejsza. Nie jest jednak jasne: co daje B P P taką moc, że obecnie nie możemy wykluczyć, że może ona nawet symulować podwójnie wykładniczy paralelizm N E X P ? Ponieważ B P P różni się jedynie postacią P przez przypadkowość, i słusznie przypuszcza się, że losowość tutaj jest bezsilna (tj. P = B P P ), wygląda mi to na dziwną sytuację. Szukam „filozoficznego zrozumienia” sytuacji poza oczywistym faktem, że brakuje narzędzi do udowodnieniaBPPBPPNEXPBPPPP=BPP . NEXPBPP
Andras Farago,
2
A jeśli tak naprawdę to po prostu brak narzędzi? Mamy twierdzenia o hierarchii, które pozwalają nam udowodnić, że więcej tego samego zasobu daje więcej mocy (np. ), a kiedy nie możemy zredukować się do twierdzenia o hierarchii, zwykle utkniemy. Jest to ogólny problem, który pojawia się na całym hierarchii złożoności, a nie coś konkretnego do B P P . PEXPBPP
Scott Aaronson
28

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 / nO(22n)O(2n)n(1+o(1))2n/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.SIZE(f(n))DTIME(f(n)O(1))f(n)2O(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.NPP/poly

Sasho Nikolov
źródło
1
Bardzo interesujące! Ładnie ilustruje to, że nasze rozumienie niejednorodnego (obwodowego) modelu obliczeń jest wciąż bardzo dalekie od pełnego.
Andras Farago
4
Bez komentowania, czy takie załamanie jest prawdopodobne: czy jest to nagłe zatrzymanie mocy obliczeniowej na drugim poziomie, kiedy to wystarczy, aby mieć oba rodzaje kwantyfikatorów?
Niel de Beaudrap,
@NieldeBeaudrap Bardzo interesujący punkt. Oczywiście wszystko to (łącznie ze spekulacjami w mojej odpowiedzi) jest bardziej teologią niż matematyką, ale fajnie jest spekulować.
Sasho Nikolov
3
@Sasho: to nie teologia, a nawet opinia: to matematyka, prawda? Jest to ewidencjonowanie pomysłów, które mogą być istotne, i rozważenie ich pod kątem intuicji. Niewiele więcej do zrobienia, gdy zagubiony w lesie, ale jest bardziej produktywny niż, powiedzmy, opowiadanie historii o duchach. :-)
Niel de Beaudrap
10

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.P/polyNPPNP

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.P/polyNP

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!NP

NPP/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ą.

chazisop
źródło
10

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ść.

András Salamon
źródło
3

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 2n 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 2nexp(O(n))=exp(nlog(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 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 P/polyNP, if we required instead the existence of proofs of at most polynomial length in n that the circuit is suitable. Notice that this restricted P/poly could still be more powerful than P. Even Karp-Lipton (i.e. that the polynomial hierarchy collapses if NPP/poly) still holds true, but this statement is less interesting than the real Karp-Lipton theorem.

Thomas Klimpel
źródło