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”? $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?

— hsalin
źródło

Odpowiedzi:

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 czasu. Dowód na to jest prosty: hipotetyczny algorytm działający w czasie 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ę liczb, istnieje 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 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ń ): $EXPTIME$ $f$

Biorąc pod uwagę funkcję , istnieje problem obliczeniowy, który można rozwiązać w czasie ale nie można go rozwiązać w czasie $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).

— Tom van der Zanden
źródło

Rozmiar wejścia lub wyjścia są najczęstszymi dolnymi granicami.

— Raphael

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 . $\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 $O(n\log n)$ chociaż wiemy, że co najmniej jedno z tych wtrąceń jest ścisłe ( według twierdzenia o hierarchii przestrzeni) i większość ludzi uważa, żewszystkiesąścisłe.

L. \subseteq N. L. \subseteq P. \subseteq N. P. \subseteq P. S. P. ZA do mi,

$\mathrm{L}\subseteq \mathrm{NL}\subseteq \mathrm{P}\subseteq \mathrm{NP} \subseteq\mathrm{PSPACE}\,,$

L \subset P S P A C E

$\mathrm{L}\subset \mathrm{PSPACE}$

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ść).

— David Richerby
źródło

Myślę, że o to mi chodzi „… musisz jakoś pokazać, że żaden algorytm w danej klasie nie jest w stanie rozwiązać twojego problemu.”, Jest to część, która wydaje mi się nieco myląca, ponieważ tak naprawdę nie mogę intuicyjnie zobaczyć, jak można to zrobić przynajmniej taka rzecz. Jak @Tom van der Zanden opisał znalezienie minimalnej liczby, którą rozumiem, ale czy takie podejście jest ogólne? Mam na myśli ogólnie rzecz biorąc, że mam taki argument przy konstruowaniu dowodów? Dziękuję również za link.

— hsalin

@ user1288420 Nie jesteś sam. Gdyby ktokolwiek mógł intuicyjnie zobaczyć, jak udowodnić, że żaden algorytm w danej klasie nie jest w stanie rozwiązać jakiegoś problemu, mielibyśmy znacznie więcej niższych wyników! Zazwyczaj musisz wymyślić jakąś właściwość, którą posiada każdy algorytm w klasie, i pokazać, że ta właściwość zapobiega rozwiązaniu jakiegoś problemu. Na przykład każda maszyna Turinga działająca w czasie podliniowym ma właściwość polegającą na tym, że nie jest w stanie odczytać wszystkich danych wejściowych. Oznacza to, że nie może rozwiązać większości problemów. To banalne; niestety, bardziej interesujące przypadki wydają się niemożliwie trudne.

— David Richerby

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

— Babou
źródło

Znalezienie wszystkich wystąpień wzorca w łańcuchu wymaga trywialnego przeczytania całego łańcucha: jeśli wzorzec jest „a”, nie można znaleźć wszystkich wystąpień bez sprawdzenia, czy każdy znak łańcucha.

— David Richerby

@DavidRicherby Właściwie nie zawsze. Algorytm Boyera-Moore'a rozpoczyna się od końca wzorca, skacząc w górę w łańcuchu. Jeśli próba dopasowania nie powiedzie się, nie musi czytać początku ciągu. Ma również optymalizację podobną do algorytmu Knuth-Morris-Pratt, aby pomijać próby, które są odrzucane ze względu na strukturę wzorca. Oczywiście istnieją wzorce, które wymagają odczytu całego łańcucha.

— babou

@DavidRicherby Dlaczego pytałeś, wiedziałeś o tym?

— babou

Nie rozumiem twojego drugiego komentarza. Twoja pierwotna odpowiedź zawierała nieprawidłowe twierdzenie. Oczywiście wiedziałem, że to nieprawda: tak mogłem to wskazać! Inni ludzie mogliby nie wiedzieć, że jest niepoprawna, więc pozostawienie takiej odpowiedzi byłoby mylące.

— David Richerby

@DavidRicherby Chodzi mi o to, że zrozumiałeś, co miałem na myśli. Powinienem powiedzieć nie może raczej niż nie . Nie wymagało to stylu komentarza, dzięki czemu czytelnicy wierzą, że mówię nonsensy. I robiąc to, popełniłeś dokładnie ten sam nieostrożny błąd: stwierdzając „ Znalezienie wszystkich wystąpień wzoru w łańcuchu wymaga trywialnego przeczytania całego łańcucha ”, gdy powinieneś był powiedzieć „ Znalezienie wszystkich wystąpień wzoru w ciągu może wymagać czytanie całego łańcucha ". Chciałem jedynie stwierdzić, że odczytanie danych wejściowych nie zawsze jest konieczne, aby złagodzić mój poprzedni przykład.

— babou