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

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?

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

$n^2$

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

$f$$f$

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.

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.

$C$$C'$$C'$$C$