Wykład ten poświęcimy problemom, które nazywamy w informatyce trudnymi. "Trudność" ich polega na braku algorytmów, które je rozwiązują w rozsądnym czasie. Większość problemów omawianych do tej pory miała rozwiązania w kosztem czasowym szacowanym przez wielomian zależny od rozmiaru danych. Takie były problemy wyszukiwania, sortowania i algorytmy grafowe. Możemy przyjąć, że koszty związane z realizacją tych algorytmów są rozsądne: dla rozsądnych rozmiarów danych, koszt czasowy wyrażony jako funkcja liniowa, liniowo-logarytmiczna, czy kwadratowa jest akceptowalny dla użytkownika. Istnieją jednak problemy, dla których nie są znane żadne algorytmy o koszcie czasowym ograniczonym przez wielomian. Do takich problemów należy wiele ważnych zadań z różnych dziedzin zastosowań, np. problem układania rozkładu zajęć, problem plecakowy, problem kolorowania grafu, problem spełniania. 

W wykładzie, poza licznymi przykładami problemów trudnych, przedstawimy krótko pojęcie NP zupełności i pojęcie rozstrzygalności. Udowodnimy ponadto, że problem stopu dla programów jest nierozstrzygalny.