Dolne granice złożoności przy użyciu algebry liniowej

Oryginalny tytuł:

Complexity Lower Bounds using Linear Algebra

Zawartość książki:

Podczas gdy poczyniono szybkie postępy w zakresie górnych granic (algorytmów), postępy w zakresie dolnych granic złożoności problemów jawnych pozostawały powolne pomimo intensywnych wysiłków podejmowanych przez kilka dekad.

Podobnie jak w przypadku typowych wyników niemożliwości, dolne granice są trudnymi problemami matematycznymi, a zatem jest mało prawdopodobne, aby można je było rozwiązać za pomocą ataków ad hoc. Zamiast tego potrzebne są techniki oparte na pojęciach matematycznych, które wychwytują złożoność obliczeniową.

Complexity Lower Bounds using Linear Algebra zawiera przegląd kilku technik dowodzenia dolnych granic złożoności boolowskiej, algebraicznej i komunikacyjnej w oparciu o pewne podejścia algebry liniowej. Wspólnym tematem tych podejść jest badanie miar odporności rangi macierzy, które wychwytują złożoność w danym modelu. Odpowiednio silne dolne ograniczenia na takie funkcje odporności macierzy jawnych prowadzą do ważnych konsekwencji w odpowiednich modelach obwodów lub komunikacji.

Zrozumienie złożoności obliczeniowej problemów ma fundamentalne znaczenie w matematyce i informatyce teoretycznej. Complexity Lower Bounds using Linear Algebra jest nieocenionym źródłem informacji dla każdego, kto pracuje w tej dziedzinie.