Czy naprawdę można udowodnić dolne granice?

Biorąc pod uwagę problem obliczeniowy, czy naprawdę jest możliwe znalezienie dolnych granic dla takiego obliczenia? Przypuszczam, że sprowadza się to do zdefiniowania pojedynczego kroku obliczeniowego i jakiego modelu używamy jako dowodu, ale biorąc pod uwagę to, czy naprawdę udowadniamy dolną granicę w ogóle? Mam na myśli to, że możemy udowodnić coś w rodzaju „problemu nie da się rozwiązać szybciej niż czas ” niż „problemu można rozwiązać w czasie lub szybciej”?t ( X ) X t ( X $X$$t(X)$$X$$t(X)$

Próbowałem znaleźć informacje na temat dolnych granic i ich dowody, ale tak naprawdę nie mogę znaleźć żadnych zainteresowań, żadnych rekomendacji na temat książek / artykułów / stron internetowych na ten temat?

Możemy absolutnie udowodnić takie rzeczy.

Wiele problemów ma trywialne dolne granice, takie jak znalezienie minimum zbioru liczb (które nie są w żaden sposób posortowane / ustrukturyzowane) zajmuje co najmniej Ω ( n ) czasu. Dowód na to jest prosty: hipotetyczny algorytm działający w czasie o ( n ) nie może zbadać wszystkich liczb na wejściu. Gdybyśmy uruchomili algorytm na niektórych danych wejściowych, moglibyśmy zaobserwować, że nigdy nie sprawdzał określonego elementu danych wejściowych. Zmieniając ten element na minimum, możemy doprowadzić algorytm do awarii.$n$$\Omega(n)$$o(n)$

Mniej trywialna dolna granica to dolna granica do sortowania w modelu porównawczym. Dowód tego jest następujący: biorąc pod uwagę liczbę n liczb, istnieje n ! możliwe wyniki (wejście może być dowolną permutacją posortowanej listy, więc wyjście może być dowolną permutacją wejścia). Jeśli ograniczamy się tylko do porównywania, wówczas nasz algorytm (średnio) musi wykonać co najmniej log 2 ( n ! ) = Ω ( n log n ) porównań, aby móc podać $\Omega(n \log n)$$n$$n!$$\log_2(n!)=\Omega(n \log n)$różne wyjścia.$n!$

Dolne granice mogą być jeszcze silniejsze. Istnieje kilka problemów (zwłaszcza problemy twarde ), dla których występuje wykładnicza dolna granica. Problemy w tej klasie obejmują obliczanie optymalnych strategii dla gier takich jak (uogólnione) szachy, warcaby i gra. Dowodem na to jest twierdzenie o hierarchii czasu , które stwierdza (z zastrzeżeniem pewnych ograniczeń f ):$EXPTIME$$f$

Biorąc pod uwagę funkcję , istnieje problem obliczeniowy, który można rozwiązać w czasie O ( f ( n ) ), ale nie można go rozwiązać w czasie o ( f ( n $f$$O(f(n))$.$o(\frac{f(n)}{\log n})$

Zasadniczo, jeśli możesz pomyśleć o funkcji , istnieje problem, który wymaga tyle czasu do rozwiązania.$f$

Wreszcie, inną drogą niekoniecznie udowodnienia dolnej granicy czasu, ale coś jeszcze silniejszego pokazuje nierozstrzygalność problemu (np. Zatrzymanie, korespondencja pocztowa).

Tak, to możliwe. Klasycznym przykładem jest fakt, że dowolny algorytm sortowania oparty na porównaniu wymaga porównań do posortowania listy długości n .$\Omega(n\log n)$$n$

Jednak dolne granice wydają się być znacznie trudniejsze do udowodnienia niż górne granice. Aby udowodnić, że istnieje algorytm sortowania, który wymaga porównań , wystarczy wykazać taki algorytm (scal sort - voila !). Ale dla dolnej granicy musisz jakoś pokazać, że żaden algorytm w danej klasie nie może rozwiązać twojego problemu. Trudność zrobienia tego ilustruje fakt, że wiemy tylko, że L ⊆ N L ⊆ P ⊆ N P ⊆ P S P A C $O(n\log n)$ chociaż wiemy, że co najmniej jedno z tych wtrąceń jest ścisłe ( L ⊂ P S P A C E według twierdzenia o hierarchii przestrzeni) i większość ludzi uważa, żewszystkiesąścisłe.

Z drugiej strony, Ryan Williams ma fajny artykuł (i rozmowę, który słyszałem kilka razy) o nazwie Algorytmy dla obwodów i obwody dla algorytmów , w którym twierdzi, że znalezienie dolnych granic i znalezienie algorytmów nie jest zasadniczo wszystkim to inaczej. Na przykład przytacza dowód nierozstrzygalności problemu zatrzymania jako przykład algorytmu (uniwersalnej maszyny Turinga) używanego właśnie do udowodnienia dolnej granicy (nierozstrzygalność).

$n$

Jest jednak punkt w pytaniu, który wymaga kilku dodatkowych uwag dotyczących dolnej granicy (lub ogólnie granic złożoności).

W rzeczywistości wybór jednego kroku obliczeniowego jest nieistotny, o ile można uznać, że kroki obliczeniowe mają stałą górną granicę (i dolną granicę). Wynik złożoności będzie taki sam, ponieważ jest zdefiniowany do stałej. Przyjmowanie 3 porównań jako operacji jednostkowych lub tylko jednej nie ma znaczenia.

To samo dotyczy wielkości danych, która służy jako odniesienie do oceny kosztów obliczeń. Biorąc jedną liczbę całkowitą lub dwie liczby całkowite jako jednostkę wielkości nie ma znaczenia.

Jednak te dwie opcje muszą być powiązane.

$n$$\log n$$O(\log n)$

To, czy operację można uznać za koszt jednostkowy, jest ściśle związane z tym, jakie dane można uznać za posiadające rozmiar jednostki. I to zależy od tego, jaki poziom abstrakcji wybierzesz dla swojego modelu obliczeniowego.