Udowadnianie dolnych granic przez udowodnienie górnych granic

29

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 NPP/poly (lub )?PNP

Mohammad Al-Turkistany
źródło
Czy to powinien być CW?
Mohammad Al-Turkistany
Lubię to, co jest (nie CW), ale wierzę, że to [soft-question].
MS Dousti,
2
@Sadeq: nie myśl, że to delikatne pytanie, jest wystarczająco precyzyjne, aby uzyskać jasną odpowiedź.
Kaveh
Wynik Meyer podkreślił Suresh pokazuje, że istnienie wielomianów obwodów dla okaże P N P . EXPPNP
Mohammad Al-Turkistany

Odpowiedzi:

23

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)

Luca Trevisan
źródło
1
Ciekawe, to świetne podsumowanie dolnych granic złożoności komunikacji! Kolejny (dziwny?) Kandydat: twierdzenie / przekątna Ladnera. Granice, oczywiście, nie są określone (ani nawet problem (y)!), Ale pokazuje superskładnikową dolną granicę dla jakiegoś problemu. Oczywiście zakłada to P NP, co można prawdopodobnie udowodnić górną granicą, a la GCT ...
Daniel Apon
14

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

Suresh Venkat
źródło
10
Jeśli policzysz twardość NP (w przeciwieństwie do oddzielenia od klasy) jako dolne granice, nie potrzebujesz twierdzenia PCP; redukcje są wydajnymi algorytmami, które dowodzą, że niektóre problemy są trudne.
Tsuyoshi Ito,
to dobra uwaga, Tsuyoshi. Jednak redukcje twardości NP są „bezpośrednie”. pokaż, że rozwiązanie nieznanego problemu rozwiązuje znany trudny problem. Niektóre z podanych tu przykładów są bardziej pośrednie. Ale to oczywiście subiektywne.
Suresh Venkat
3
Samo stwierdzenie twierdzenia PCP to kompletność NP Gap-3SAT. Co więcej, nie wiem, co miałeś na myśli, twierdząc, że twierdzenie PCP jest pośrednie. To prawda, że ​​twierdzenie PCP wymaga jednego z najbardziej skomplikowanych dowodów spośród wyników NP-kompletności, ale czy to dobrze?
Tsuyoshi Ito,
Suresh, czy mógłbyś zamieścić tutaj, jako nową odpowiedź, rozszerzoną wersję dwóch przykładów, do których odwoływałeś się w odpowiedzi na inne pytanie (wynik Meyera i GCT)?
Mohammad Al-Turkistany
jakiś powód dlaczego? Nie mam z tym problemu, ale czy jest to konieczne, skoro zacytowałeś to w pytaniu?
Suresh Venkat
12

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 .

Marc
źródło
11

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 ( CIbitów - ulepszona górna granica.O~(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 fnkfrazem - Udoskonalony dolnej granicy.kn

Daniel Apon
źródło
7

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ć:

NPP/polyPH=Σ2p=Π2p

NPP/polyAM=MA

coNPNP/polyPH=Σ3p=Π3p

MS Dousti
źródło
5

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

CC1Cm

PNP

Mohammad Al-Turkistany
źródło
5

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

EXPo(2n/n)PNP

Mohammad Al-Turkistany
źródło