Przykład intuicyjny Typowym przykładem jest problem spełnialności formuł logicznych. Dla danej formuły rachunku zdań łatwo sprawdzić, czy konkretne przypisanie wartości logicznych spełnia tę formułę: wystarczy podstawić wartości zmiennych i obliczyć wynik. Znacznie trudniejsze może być znalezienie takiego przypisania lub stwierdzenie, że ono nie istnieje. Problem spełnialności, znany jako SAT, jest centralnym przykładem problemu NP-zupełnego. Z SAT wiąże się silniejsza od hipotezy P ≠ NP hipoteza czasu wykładniczego, według której 3-SAT nie ma algorytmu podwykładniczego, tj. działającego w czasie gdzie oznacza liczbę zmiennych formuły. Impagliazzo, Paturi i Zane pokazali, że podwykładnicze algorytmy dla wielu naturalnych problemów NP-zupełnych są powiązane redukcjami zachowującymi taki czas działania.
Podobny kontrast między łatwym sprawdzeniem a trudnym znalezieniem rozwiązania występuje w wielu łamigłówkach i zadaniach kombinatorycznych. Uzupełnioną planszę uogólnionego sudoku albo kwadrat łaciński łatwo zweryfikować, lecz istnienie takiego wypełnienia dla uogólnionego sudoku oraz uzupełnianie częściowych kwadratów łacińskich to problemy NP-zupełne.