Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 15

Problemy obliczeniowe występują w rozmaitych odmianach; niektóre są łatwe, inne naprawdę trudne. Na przykład problem sortowania należy do tych łatwych. Załóżmy, że potrzebujemy uporządkować listę liczb w kolejności rosnącej. Nawet niewielki komputer potrafi dość szybko posortować milion liczb. Porównajmy to z problemem planu zajęć. Załóżmy, że musimy znaleźć plan wykładów dla całego uniwersytetu, spełniając pewne rozsądne ograniczenia, takie jak to, że żadne dwa wykłady nie mogą odbywać się w tej samej sali w tym samym czasie. Problem planowania wydaje się znacznie trudniejszy niż problem sortowania. Jeśli mamy choćby tysiąc grup, znalezienie najlepszego planu zajęć może trwać wieki, nawet przy użyciu superkomputera.

Co sprawia, że pewne problemy są obliczeniowo trudne, a inne łatwe?

Jest to centralne zagadnienie teorii złożoności. Co istotne, nie znamy na nie odpowiedzi, mimo że intensywne poszukiwania trwają od ponad 40 lat. Później zbadamy bliżej to fascynujące pytanie i niektóre z jego wariantów.

W jednym z ważnych osiągnięć teorii złożoności, jakie udało się uzyskać do tej pory, badacze odkryli elegancki schemat klasyfikowania problemów w zależności od ich trudności obliczeniowej. Jest on analogiczny do tablicy okresowej pierwiastków, stosowanej do klasyfikowania ich według własności chemicznych. Używając tego schematu, możemy wskazać metodę znajdowania przesłanek, że określone problemy są trudne obliczeniowo, nawet jeśli nie będziemy w stanie udowodnić, że takie są.

Stając w obliczu problemu, który wydaje się trudny obliczeniowo, mamy do dyspozycji kilka opcji. Po pierwsze, przez zrozumienie, jaki aspekt problemu jest źródłem tej trudności, możemy być w stanie zmienić go tak, aby problem stał się łatwiejszy do rozwiązania. Po drugie, może się okazać, że niedoskonałe rozwiązanie jest wystarczające. W określonych sytuacjach znalezienie takiego, które jest jedynie przybliżeniem najlepszego, jest łatwe. Po trzecie, niektóre problemy są trudne tylko w najgorszym przypadku, ale w większości pozostałych sytuacji są łatwe. Zależnie od zastosowania możemy być usatysfakcjonowani procedurą, która okazjonalnie jest bardzo powolna, ale zazwyczaj działa szybko. Na koniec wreszcie można rozważyć alternatywne rodzaje przetwarzania, takie jak obliczenia randomizowane, co pozwala przyśpieszyć określone zadania.

Jednym z obszarów zastosowań, na który teoria złożoności ma bezpośredni wpływ, jest starożytna dziedzina kryptografii. W większości zagadnień problemy łatwe obliczeniowo są preferowane względem tych trudnych, gdyż rozwiązywanie łatwych jest tańsze. Kryptografia jest nietypowa, gdyż stawiane jest wymaganie, aby problemy obliczeniowe były trudne, a nie łatwe. Tajne szyfry powinny być trudne do złamania bez znajomości tajnego klucza czy hasła. Teoria złożoności nakierowała kryptografów w stronę problemów trudnych obliczeniowo, na podstawie których zostały zaprojektowane nowe szyfry.