Złożoność obliczeniowa

W ostatnich latach nastąpił gwałtowny rozwój technologii komputerowych. Maszyny są coraz szybsze, mają coraz większą pamięć, przetwarzają dźwięk i obrazy. Nie udało się jednak dotychczas rozwiązać wielu zadań obliczeniowych, które wymagają długiego czasu pracy komputera. Jak sobie z tym poradzić?
Odpowiedź na to pytanie znajduje się w tej książce. Jest to najlepszy podręcznik z teorii złożoności obliczeniowej. Autor w bardzo przystępny sposób wprowadza Czytelnika w tajniki algorytmów i barier obliczalności. Omawia najważniejsze problemy związane z maszynami Turinga, obliczalnością, problemem P=NP, obliczeniami równoległymi i ich związkami z obliczeniami w małej pamięci. Przedstawia też zagadnienia dotyczące hierarchii wielomianowej, zliczania i obliczeń z ograniczoną pamięcią.
Książka jest przeznaczona dla studentów informatyki. Powinna być podstawowym podręcznikiem do przedmiotów: „Algorytmy i struktury danych”, „Języki, automaty i obliczenia”, „Teoria złożoności obliczeniowej” i „Modele obliczeń”. Dzisiaj każdy, kto zajmuje się informatyką, musi zrozumieć naturę obliczeń, a co za tym idzie zdawać sobie sprawę z możliwości i ograniczeń współczesnych komputerów.