Udowadnianie dolnych granic przez udowodnienie górnych granic

Niedawny wynik Ryana Williamsa w przełomowym złożoności obwodu w dolnej granicy zapewnia technikę dowodową, która wykorzystuje wynik górnej granicy w celu udowodnienia niższych granic złożoności. Suresh Venkat w swojej odpowiedzi na to pytanie: Czy są jakieś sprzeczne z intuicją wyniki w informatyce teoretycznej? , podał dwa przykłady ustanawiania dolnych granic przez udowodnienie górnych granic.

• Jakie są inne interesujące wyniki dla udowodnienia dolnych granic złożoności, które zostały uzyskane przez udowodnienie górnych granic złożoności?

• Czy istnieje jakieś górne ograniczenie, które sugerowałoby $NP \not\subseteq P/poly$ (lub )?$P \ne NP$

Można odwrócić to pytanie i zapytać, jakie dolne granice nie są udowodnione przez udowodnienie górnej granicy. Prawie wszystkie dolne granice złożoności komunikacyjnej (i dolne granice algorytmu strumieniowania i dolne granice struktury danych, które opierają się na argumentach złożoności komunikacyjnej) zostały udowodnione poprzez wykazanie, że protokół komunikacyjny można konstruktywnie przekształcić w schemat kodowania, przy czym długość kodowania zależy od złożoność komunikacji protokołu, a dolna granica protokołu wynika z faktu, że nie można zakodować wszystkich n bitów wiadomości przy użyciu n-1 bitów lub mniej.

Obwody Razborova-Smoleńskiego działają poprzez pokazanie, jak symulować obwody o ograniczonej głębokości za pomocą wielomianów niskiego stopnia.

Dwoma kandydatami na dolne granice, które nie zostały udowodnione górną granicą, może być twierdzenie o hierarchii czasu (chociaż aby uzyskać najściślejsze granice, potrzebna jest wydajna uniwersalna maszyna Turinga, która jest nietrywialnym zadaniem algorytmicznym) i dowód dolnych granic AC0 za pomocą lematu przełączającego (ale najczystszy dowód lematu przełączającego wykorzystuje liczenie / nieściśliwość / złożoność Kołmogorowa)

W dziwny sposób samo twierdzenie PCP jest dobrym przykładem dowodzenia dolnej granicy poprzez górną granicę. „Skuteczna” randomizowana strategia weryfikacji dowodu przy użyciu stałej liczby sond dowodu i tylko losowych bitów prowadzi do dolnej granicy przybliżenia liczby spełnionych klauzul w przypadku 3SAT.$\log n$

Metoda nieściśliwości jest metodą opartą na złożoności Kołmogorowa w celu udowodnienia dolnych granic. Jednym z pierwszych zastosowań tej metody było udowodnienie, że rozpoznanie palindromów na maszynie Turinga za pomocą pojedynczej taśmy wymaga kwadratowego czasu.

Luźno mówiąc, ideą tej metody jest opisanie procedury znalezienia danych wejściowych przy użyciu informacji zawartych w przebiegu algorytmu rozwiązującego problem, który rozważamy na tych danych wejściowych. Im lepsza jest procedura, tym wyższa jest dolna granica pierwotnego problemu.

Oczywiście pełne informacje można znaleźć w podręczniku Li i Vitanyi .

W przypadku pytania „dolna granica przez górną granicę” zadałeś:

W artykule STOC 2010 „Jak skompresować komunikację interaktywną” [BBCR10] przedstawiono ulepszone twierdzenie o bezpośredniej sumie dla losowej złożoności komunikacji, demonstrując ulepszony protokół kompresji dla komunikacji interaktywnej.

W szczególności, biorąc pod uwagę, że dwie strony obliczają jakąś wspólną funkcję swoich wzajemnych danych wejściowych (tj. Interaktywny scenariusz obliczeniowy), pokazują one, że każdy protokół, który komunikuje bity i ujawnia I bitom nowych danych zainteresowanym stronom, może być symulowany przez nowy protokół przy użyciu ˜ O ( $C$$I$bitów - ulepszona górna granica.$\tilde O(\sqrt{CI})$

W wyniku tej ulepszonej kompresji protokołu pokazują, że w najgorszym przypadku: Biorąc pod uwagę dowolną funkcję która zajmuje n czasu na indywidualne obliczenie, obliczenie k kopii f wymaga co najmniej $f$$n$$k$$f$razem - Udoskonalony dolnej granicy.$\sqrt{k} \cdot n$

To w jakiś sposób różni się od tego, o co prosiłeś, ale ponieważ jest to powiązane, pomyślałem, że mógłbym o tym wspomnieć.

Carter i Wegman (1977) wprowadzili pojęcie uniwersalnego mieszania . Pojęcie to zostało wykorzystane w wielu artykułach ( Sipser (1983) , Stockmeyer (1983) , Babai (1985) i Goldwasser & Sipser (1986) ), aby udowodnić przybliżone dolne granice .

Tak było do 1987 roku, kiedy to Fortnow użył uniwersalnego haszowania, aby udowodnić przybliżone górne granice . (W rzeczywistości, aby zapewnić protokół potwierdzający przybliżone górne granice).

Edytować:

To nie są wyniki z dolnej granicy, ale i tak mogą się przydać:

$\rm{NP} \subset \rm{P/poly} \quad \Rightarrow \quad \rm{PH}=\rm{\Sigma_2^p}=\rm{\Pi_2^p}$

$\rm{NP} \subset \rm{P/poly} \quad \Rightarrow \quad \rm{AM}=\rm{MA}$

$\rm{coNP} \subset \rm{NP/poly} \quad \Rightarrow \quad \rm{PH}=\rm{\Sigma_3^p}=\rm{\Pi_3^p}$

Znalazłem piękny przykład w blogu Dicka Lipton, w Podejście do P = NP poprzez Complexity opisowa , Proponuje on górną granicę przypuszczenie (hipotezę H), który oznaczałby .$P\ne NP$

$C$$C_{1} \wedge \dots \wedge C_{m}$

$P \ne NP$

Oto przykład złożoności obliczeniowej: nowoczesne podejście Arory i Baraka (strona 128):

$EXP$$o(2^{n} /n)$$P \ne NP$