Czy istnieje wytłumaczenie trudności w udowodnieniu kwadratowych dolnych granic dla interesujących problemów NP?

11

To kontynuacja mojego poprzedniego pytania:

Najbardziej znana deterministyczna złożoność czasu dolna granica naturalnego problemu w NP

Uważam za zdumiewające, że nie byliśmy w stanie udowodnić żadnego kwadratowego deterministycznego czasu w dolnej granicy jakiegokolwiek interesującego problemu NP, na który ludzie dbają i starają się zaprojektować lepsze algorytmy. Nasza hipoteza o wykładniczym czasie zakłada, że ​​SAT nie można rozwiązać w podwykładniczym deterministycznym czasie, ale nie możemy nawet udowodnić, że SAT (lub jakikolwiek inny interesujący problem NP) wymaga kwadratowego czasu!

Wiem, że interesujące jest nieco subiektywne i niejasne. Nie mam definicji. Ale pozwólcie, że spróbuję opisać to, co uważam za interesujący problem: mówię o problemach, które są interesujące dla kilku osób. Nie mówię o odosobnionych problemach zaprojektowanych głównie w celu odpowiedzi na niektóre pytania teoretyczne. Jeśli ludzie nie próbują znaleźć szybszych algorytmów dla problemu, oznacza to, że problem nie jest tak interesujący. Jeśli chcesz konkretnych przykładów interesujących problemów, rozważ problemy w pracy Karpa z 1972 r. Lub w Garey and Johnson 1979 (większość z nich).

Czy jest jakieś wytłumaczenie, dlaczego nie byliśmy w stanie udowodnić żadnego kwadratowego deterministycznego czasu dolnej granicy jakiegokolwiek interesującego problemu NP?

Anonimowy
źródło
3
Ponieważ dolne granice są trudne? Jakie wyjaśnienie by Cię zadowoliło?
Jeffε
3
@ Jɛ ff E co powiesz na nietrywialne wyjaśnienia, które są pouczające i wnikliwe? Intuicja lub wyniki wyjaśniające, dlaczego utknęliśmy w miejscu, w którym dowodzimy niższych granic. Ponieważ nasze twierdzenia były znacznie silniejsze niż nasze wyniki, jestem pewien, że inni eksperci zastanawiali się, dlaczego po dziesięcioleciach prób nie byliśmy w stanie uzyskać kwadratowej dolnej granicy interesującego problemu NP.
Anonimowy
3
Oto wyjaśnienie z blogu Lipton; Przynęta i zamiana: dlaczego dolne granice są tak trudne? rjlipton.wordpress.com/2009/02/12/…
Mohammad Al-Turkistany
3
n2
2
Kwestia kwadratowych granic czasowych jest istotna, gdy ograniczysz algorytmy, aby mieć bardzo mało miejsca (np. Polilog), lub gdy spojrzysz na maszyny Turinga z jedną taśmą (które mają bardzo ograniczony dostęp do pamięci). Ale kiedy pamięć jest nieograniczona, a dostęp do pamięci nieograniczony, „prawdziwym” pytaniem jest, czy istnieją dolne granice czasu superliniowego dla interesujących problemów NP, w dowolnym modelu obliczeniowym o dostępie swobodnym. (Grandjean udowodnił pewne superliniowe dolne granice dla wielowarstwowych maszyn Turinga, ale polegają one na strukturze jednowymiarowych taśm.)
Ryan Williams

Odpowiedzi:

5

Oto wyjaśnienie z blogu Liptona: Bait and Switch: Dlaczego niższe granice są tak trudne?

n2

Wgląd Rudicha wyjaśnia, dlaczego żaden dolny limit dowodu, że jest oparty na poniższej metodzie, nie może działać.

ff

Zasadniczo nie ma miar postępu, który byłby w stanie przetrwać sztuczkę Bait and Switch Rudicha i z powodzeniem prowadzi do dolnej granicy.

Mohammad Al-Turkistany
źródło
4

Inne spojrzenie na argument „przynęta i zamiana” znajduje się w rozdziale Arora-Barak dotyczącym naturalnych dowodów . Używają tego samego argumentu, aby argumentować, że dolny limit w stylu „miara złożoności formalnej” musi mieć zastosowanie do funkcji losowych z dużym prawdopodobieństwem. Ale jeśli formalna miara złożoności

  1. przypisuje dużą złożoność funkcji losowej
  2. nie przypisuje wysokiej złożoności łatwej funkcji
  3. można łatwo obliczyć z tabeli prawdy funkcji

następnie można go użyć do przerwania generatorów pseudolosowych. Taka jest bariera naturalnych dowodów, nieformalnie. Argumentowaliśmy, że 1. jest bardzo rozsądny w przypadku wielu podejść do dolnych granic, bez 2. miara złożoności wydaje się bezużyteczna, a 3. opiera się na spostrzeżeniu, że udało nam się przekształcić większość kombinatorycznych dowodów istnienia w wydajne algorytmy oraz na podstawie intuicja, że ​​z natury niekonstruktywny dowód jest trudny do opracowania.

CCCC

Sasho Nikolov
źródło