Złożoność parametryzowana nie pyta tylko o całkowity rozmiar wejścia n. Wybiera dodatkowy parametr k — na przykład liczbę wyjątków, wielkość szukanego rozwiązania albo szerokość struktury — i próbuje uzyskać czas f(k)·n^c, gdzie wykładnik c nie zależy od k. Takie problemy nazywa się fixed-parameter tractable, FPT. Funkcja f(k) może rosnąć bardzo szybko, nawet wykładniczo, ale jeśli k pozostaje małe, ogromne n nie musi być zabójcze. To inny sposób radzenia sobie z NP-trudnością: zamiast udawać, że całe wejście jest łatwe, izolujemy część odpowiedzialną za eksplozję kombinatoryczną.
Klasyczny problem plecakowy ma programowanie dynamiczne działające w czasie O(n·C), gdzie n to liczba przedmiotów, a C — pojemność plecaka wyrażona jako liczba całkowita. Na pierwszy rzut oka to wielomian. Problem w tym, że wielkością wejścia jest liczba bitów potrzebnych do zapisania C, czyli około log2 C. Jeżeli C jest ogromne, algorytm zależny od samej wartości C może być wykładniczy względem długości jej zapisu. Taki czas nazywa się pseudowielomianowym. Plecak jest słabo NP-trudny właśnie w sposób zgodny z istnieniem takich algorytmów. To lekcja, że w analizie złożoności nie pytamy tylko „jak duża jest liczba?”, lecz „ile informacji trzeba było dostarczyć, aby ją zapisać?”.
Funkcja Busy Beaver jest zdefiniowana za pomocą bardzo małych maszyn Turinga. W jednej z klasycznych wersji pytamy o maksymalną liczbę kroków wykonaną przed zatrzymaniem przez dowolną zatrzymującą się maszynę o n stanach uruchomioną na pustej taśmie. Dla każdego n maksimum istnieje, bo rozważamy skończenie wiele maszyn danego typu. Mimo to funkcji nie da się obliczać dla dowolnego n. Co więcej, jej wzrost ostatecznie przewyższa każdą funkcję obliczalną. Gdybyśmy mieli obliczalną górną granicę czasu zatrzymania takich maszyn, moglibyśmy uruchomić każdą odpowiednio długo i rozstrzygnąć, które nigdy się nie zatrzymają — a to dałoby rozwiązanie problemu stopu.
W problemach optymalizacyjnych wymaganie absolutnie najlepszego rozwiązania może być źródłem trudności. Klasyczny problem plecakowy jest NP-trudny, ale ma FPTAS — w pełni wielomianowy schemat aproksymacyjny. Dla dowolnego ε>0 algorytm może znaleźć rozwiązanie o wartości co najmniej (1−ε) optimum, działając w czasie wielomianowym zarówno względem długości wejścia, jak i 1/ε. Użytkownik może więc świadomie zamienić niewielką utratę jakości na przewidywalny czas. Nie jest to uniwersalny trik dla wszystkich NP-trudnych problemów, lecz pokazuje ważny sposób obchodzenia granic: czasem nie zmieniamy sprzętu ani problemu, tylko precyzję wymaganej odpowiedzi.
2-SAT i 3-SAT wyglądają niemal identycznie: w obu szukamy wartości prawda/fałsz dla zmiennych tak, aby spełnić formułę logiczną w postaci koniunkcji klauzul. Różnica polega na maksymalnej liczbie literałów w klauzuli. Dla 2-SAT istnieje algorytm liniowy oparty na grafie implikacji i silnie spójnych składowych. 3-SAT jest natomiast jednym z klasycznych problemów NP-zupełnych. To niezwykły przykład „progu złożoności”: pozornie drobne rozszerzenie lokalnego warunku z dwóch do trzech literałów wystarcza, by przejść od problemu efektywnie rozwiązywalnego do problemu reprezentującego pełną trudność NP.
Dwa klasyczne pytania o przejście przez graf brzmią niemal jak rodzeństwo. Ścieżka Eulera ma użyć każdej krawędzi dokładnie raz; ścieżka Hamiltona ma odwiedzić każdy wierzchołek dokładnie raz. Dla nieskierowanego grafu istnienie ścieżki Eulera można rozpoznać z prostych warunków stopni i spójności, a samą trasę znaleźć w czasie liniowym względem liczby krawędzi. Problem ścieżki Hamiltona jest NP-zupełny. Różnica pokazuje, że „odwiedzić wszystko po jednym razie” nie jest jedną klasą trudności: znaczenie ma to, czy pilnujemy lokalnych krawędzi, czy globalnego wyboru kolejności wierzchołków.
Komputery kwantowe mogą radykalnie przyspieszać niektóre zadania, ale nie ma podstaw, by utożsamiać je z maszynami rozwiązującymi wszystkie problemy NP-zupełne w czasie wielomianowym. Nie znamy ogólnego wielomianowego algorytmu kwantowego dla problemów NP-zupełnych; wyniki w modelach oracle dostarczają nawet formalnych ograniczeń dla pewnych rodzajów przyspieszeń. Również standardowy model obliczeń kwantowych nie jest traktowany jako sposób na obejście klasycznej nierozstrzygalności: zmienia złożoność niektórych obliczeń, ale nie daje zwykłego algorytmu dla problemu stopu. „Kwantowy” oznacza inny model zasobów, nie zniesienie logiki obliczalności.
W grafie znalezienie najkrótszej drogi jest klasycznym problemem z wydajnymi algorytmami: dla nieujemnych wag działa algorytm Dijkstry, a w grafie nieważonym wystarcza BFS. Bardzo podobnie brzmiący problem znalezienia najdłuższej prostej ścieżki — bez powtarzania wierzchołków — jest w ogólnych grafach NP-trudny. Różnica bierze się z warunku „prosta”. Bez niego dodatni cykl pozwalałby dowolnie wydłużać drogę przez krążenie w kółko. Z warunkiem zakazu powtórzeń trzeba wybierać globalnie, które wierzchołki wykorzystać i w jakiej kolejności, a problem zawiera w sobie ścieżkę Hamiltona jako przypadek szczególny.
Złożoność Kołmogorowa ciągu danych to, w uproszczeniu, długość najkrótszego programu, który potrafi ten ciąg wygenerować na ustalonej uniwersalnej maszynie. Brzmi jak idealna definicja „prawdziwej kompresowalności”: prosty napis powinien mieć krótki program, losowo wyglądający — długi. Problem polega na tym, że złożoność Kołmogorowa nie jest funkcją obliczalną. Nie ma algorytmu, który dostaje dowolny ciąg, zawsze kończy i podaje długość absolutnie najkrótszego programu generującego ten ciąg. Aby mieć pewność, że krótszy kandydat nigdy niczego nie wypisze, musielibyśmy rozwiązywać problem stopu.
Dziesiąty problem Hilberta pytał o ogólną procedurę, która dla wielomianowego równania z całkowitymi współczynnikami rozstrzygnie, czy istnieje rozwiązanie w liczbach całkowitych. Odpowiedź okazała się negatywna. Prace Davisa, Putnama, Robinson i ostateczny krok Jurija Matiyasevicha doprowadziły do wyniku, że nie istnieje algorytm rozwiązujący ten problem dla wszystkich równań diofantycznych. To niezwykłe, bo każde konkretne podstawienie liczb można łatwo sprawdzić, a rozwiązania można systematycznie wyszukiwać. Nie ma jednak uniwersalnej procedury, która zawsze potrafi również potwierdzić brak rozwiązania i zakończyć pracę.
Twierdzenie Rice’a rozszerza intuicję problemu stopu. Dla programów o mocy maszyny Turinga każda nietrywialna własność semantyczna obliczanej funkcji lub rozpoznawanego języka jest nierozstrzygalna w pełnej ogólności. „Semantyczna” oznacza, że pytamy o to, co program robi, a nie jak wygląda jego kod; „nietrywialna” — że własność ma przynajmniej jeden program, który ją posiada, i przynajmniej jeden, który jej nie posiada. Dlatego nie istnieje doskonały analizator odpowiadający dla dowolnego programu na pytania typu „czy zawsze zwraca zero?” albo „czy oblicza dokładnie tę funkcję?”. Narzędzia praktyczne działają dzięki ograniczeniom i aproksymacji.
Problem stopu nie jest problemem „bardzo trudnym” w tym samym sensie co NP-zupełność. Jest nierozstrzygalny: nie istnieje algorytm, który dla każdego możliwego programu i każdego wejścia zawsze kończy pracę i poprawnie odpowiada, czy analizowany program kiedyś się zatrzyma. Dowód wykorzystuje samoodniesienie i diagonalizację. Gdyby istniał doskonały tester HALT, można byłoby zbudować program, który po zapytaniu testera robi dokładnie odwrotnie w specjalnym przypadku dotyczącym samego siebie, prowadząc do sprzeczności. Ograniczenie jest logiczne, nie sprzętowe — miliard razy szybszy komputer nie pomaga, bo poszukiwany uniwersalny algorytm po prostu nie istnieje.
Uniwersalny bezstratny kompresor, który skraca każdy plik i nigdy żadnego nie wydłuża, jest niemożliwy z prostego powodu kombinatorycznego. Dla plików długości n bitów istnieje 2^n różnych wejść. Wszystkich krótszych ciągów bitów — długości 0,1,…,n−1 — jest łącznie tylko 2^n−1. Nie wystarcza ich, aby każdemu n-bitowemu plikowi przypisać inny krótszy kod, a bezstratna dekompresja wymaga jednoznaczności. Jeśli kompresor skraca pewne dane, musi pozostawić inne bez skrócenia lub je powiększyć. Skuteczna kompresja działa dlatego, że realne dane nie są równomiernie losowe i mają regularności, które kodek potrafi wykorzystać.
Dla dowolnych programów o pełnej mocy obliczeniowej problem równoważności — czy oba zachowują się tak samo dla wszystkich możliwych wejść — jest nierozstrzygalny. Nie istnieje więc uniwersalny program, który bierze dwie dowolne implementacje, zawsze kończy i bezbłędnie odpowiada „tak” lub „nie” na pytanie o ich pełną równoważność. Dowód można uzyskać przez redukcję z problemu stopu. To nie oznacza, że kompilatory nie mogą udowadniać poprawności optymalizacji ani że testy są bezużyteczne. Oznacza, że w pełnej ogólności trzeba korzystać z ograniczonych klas programów, formalnych dowodów dla konkretnych przypadków lub metod, które czasem nie potrafią rozstrzygnąć.
P kontra NP pyta w uproszczeniu: jeżeli poprawność rozwiązania można sprawdzić w czasie wielomianowym, czy rozwiązanie można też w takim czasie znaleźć? Klasa P obejmuje problemy rozwiązywalne efektywnie przez deterministyczny algorytm, a NP — problemy z efektywnie weryfikowalnym certyfikatem odpowiedzi „tak”. Wiemy, że P jest zawarte w NP, ale do dziś nie wiadomo, czy P=NP, czy P≠NP. Według Clay Mathematics Institute problem pozostaje nierozwiązany. Gdyby P=NP, wszystkie problemy NP-zupełne miałyby algorytmy wielomianowe; gdyby P≠NP, istniałaby formalna granica między szybkim sprawdzaniem a szybkim rozwiązywaniem.
Teoria złożoności nie mierzy wyłącznie czasu. Klasa PSPACE obejmuje problemy rozstrzygalne przy użyciu pamięci ograniczonej wielomianem długości wejścia, nawet jeśli obliczenie może trwać bardzo długo. Klasycznym problemem PSPACE-zupełnym jest TQBF — sprawdzanie prawdziwości w pełni skwantyfikowanych formuł boolowskich. Prosty algorytm rekurencyjny może rozgałęziać się na wiele przypisań, ale nie musi przechowywać całego drzewa naraz: eksploruje gałęzie po kolei i ponownie wykorzystuje pamięć. To pokazuje, że czas i pamięć są różnymi zasobami. Program może wykonywać olbrzymią liczbę kroków, a mimo to utrzymywać stosunkowo niewielki stan roboczy.
Przez lata istniały szybkie testy probabilistyczne pierwszości, lecz brakowało bezwarunkowego deterministycznego algorytmu wielomianowego znanego dla wszystkich wejść. Przełom przyniosła praca Manindry Agrawala, Neeraja Kayala i Nitina Saxeny: „PRIMES is in P”. Autorzy przedstawili deterministyczny algorytm działający w czasie wielomianowym względem długości binarnego zapisu liczby. To ważna lekcja o granicach wiedzy: fakt, że przez długi czas nie znamy szybkiego algorytmu, nie dowodzi, że problem jest fundamentalnie trudny. Trzeba też odróżniać testowanie pierwszości od faktoryzacji — to różne problemy o różnym znanym statusie złożoności.
W programowaniu liniowym zmienne mogą przyjmować wartości rzeczywiste, a ograniczenia i funkcja celu są liniowe. Wiemy, że takie problemy można rozwiązywać w czasie wielomianowym. Wystarczy jednak dodać wymóg, aby zmienne były całkowite — na przykład 0 lub 1, bo maszyny nie można kupić „w 0,37 sztuki” — a ogólne programowanie całkowitoliczbowe staje się NP-trudne. To zaskakujący kontrast: równania mogą wyglądać prawie tak samo, lecz dyskretność rozrywa ciągłą przestrzeń rozwiązań na ogromny zbiór kombinacji. Z tego powodu relaksacja LP jest często używana jako narzędzie pomagające rozwiązywać trudne ILP, ale zaokrąglenie wyniku nie zawsze daje poprawne ani dobre rozwiązanie.
Liczba rzeczywista jest obliczalna, jeśli istnieje skończony algorytm potrafiący przybliżać ją z dowolnie zadaną dokładnością. π, e czy √2 spełniają ten warunek. Zaskoczenie pojawia się przy policzeniu „ile” takich liczb istnieje. Programy są skończonymi napisami nad skończonym alfabetem, więc jest ich tylko przeliczalnie wiele. Każdy program może definiować najwyżej określoną liczbę rzeczywistą w danym schemacie obliczania, więc liczb obliczalnych jest co najwyżej przeliczalnie wiele. Zbiór wszystkich liczb rzeczywistych jest nieprzeliczalny. Co więcej, każdy zbiór przeliczalny ma miarę Lebesgue’a zero — zatem w standardowym sensie miary „prawie każda” liczba rzeczywista jest nieobliczalna.
W teorii złożoności istnieje ważna asymetria: dla wielu problemów ktoś może podać krótkie „świadectwo” poprawnej odpowiedzi, które da się szybko sprawdzić, mimo że nie znamy równie szybkiego sposobu znalezienia takiego świadectwa od zera. To intuicja stojąca za klasą NP. Przykładowo, jeśli dostaniemy kolejność wierzchołków rzekomo tworzącą ścieżkę Hamiltona, możemy szybko sprawdzić, czy każdy wierzchołek występuje dokładnie raz i czy kolejne są połączone. Znalezienie takiej ścieżki w dowolnym grafie to jednak problem NP-zupełny. Ważne: NP nie oznacza „niewielomianowe” ani „niemożliwe”; chodzi o szybko weryfikowalne odpowiedzi.
NP-zupełność opisuje najgorszy przypadek całej klasy instancji, nie gwarantuje, że każda rzeczywista formuła SAT będzie trudna. Nowoczesne solvery konfliktowe, zwłaszcza CDCL, nie przeglądają po prostu wszystkich 2^n przypisań. Uczą się z konfliktów, dodając nowe klauzule blokujące całe rodziny błędnych decyzji, korzystają z dynamicznych heurystyk wyboru zmiennych, restartów i usuwania mniej użytecznych klauzul. Dzięki temu potrafią rozwiązywać bardzo duże ustrukturyzowane problemy z weryfikacji sprzętu, planowania czy model checking. Nie przeczy to NP-zupełności: nadal mogą istnieć instancje wymagające ogromnej pracy i nie znamy wielomianowej gwarancji dla wszystkich przypadków.
Jeżeli algorytm wymaga sprawdzenia około 2^n możliwości, ogromny wzrost mocy sprzętu może dać zaskakująco mały zysk. Komputer tysiąc razy szybszy nie pozwala wtedy zwiększyć n tysiąckrotnie, lecz tylko o około 10, bo 2^10 ≈ 1000. Nawet miliardkrotne przyspieszenie odpowiada zaledwie około 30 dodatkowym elementom. To istota eksplozji kombinatorycznej: liczba przypadków rośnie szybciej, niż sprzęt potrafi ją dogonić. Dlatego w informatyce przełomem bywa nie szybszy procesor, lecz znalezienie algorytmu o zupełnie lepszym tempie wzrostu czasu działania.
NP-zupełność ujawniła zaskakującą jedność między problemami wyglądającymi na niepowiązane. Redukcja wielomianowa jest algorytmicznym „tłumaczeniem”: przekształca przypadek jednego problemu w przypadek drugiego tak, aby odpowiedź została zachowana. Twierdzenie Cooka z 1971 r. pokazało fundamentalną kompletność problemu logicznego związanego z SAT, a Richard Karp w 1972 r. wykazał podobne relacje dla szerokiej grupy problemów kombinatorycznych. Efekt jest niezwykły: szybki algorytm dla jednego problemu NP-zupełnego dałby szybkie algorytmy dla wszystkich problemów w NP. Trudność może więc być przenoszona między logiką, grafami, harmonogramami i innymi dziedzinami.
Kafelki Wanga to kwadraty z kolorami na czterech krawędziach. Dostajemy skończony zestaw typów i nieograniczoną liczbę kopii; sąsiednie krawędzie muszą mieć ten sam kolor. Pytanie brzmi, czy danym zestawem można pokryć całą nieskończoną płaszczyznę. Robert Berger udowodnił, że ogólny „domino problem” jest nierozstrzygalny. Nie istnieje algorytm, który dla każdego skończonego zestawu kafelków zawsze poprawnie zdecyduje, czy takie nieskończone ułożenie istnieje. Konstrukcje potrafią kodować przebieg maszyny Turinga, więc pytanie geometryczne dziedziczy granice problemu stopu.
