Złożoność obliczeniową programu komputerowego lub algorytmu rozumie
się jako wzór z jedną zmienną określający ile kroków potrzeba w najgorszym przypadku do zakończenia pracy programu. Analogicznie
złożoność obliczeniowa problemu obliczeniowego to taka formuła, dla której istnieje najszybszy program realizujący takie obliczenia. Użyta w formule zmienna uzależnia wynik od wielkości wprowadzonych danych, bowiem logiczne jest, że szybciej wykonamy obliczenie kosztu zakupu kilku artykułów w sklepie niż inwenturę całego tego sklepu z tysiącami artykułów. W tym przypadku szybkość obliczeń zależy liniowo od wielkości danych wejściowych. Ale nie zawsze tak jest. Bowiem np. wzajemne powitanie jednocześnie przybywających uczestników przyjęcia zależy już od kwadratu liczby tych uczestników (trzeba wykonać n x (n-1)/2 ukłonów lub uścisków dłoni). A np. jeden z problemów układania krzyżówki o zadanej strukturze z zadanego zbioru słów nie daje się rozwiązać szybciej niż rośnie formuła zawierająca zmienną w wykładniku. O tych ostatnich problemach mówimy, że mają złożoność ekspotencjalną, gdy te poprzednie miały złożoność wielomianową. Artykuł dotyczy złożoności obliczeniowej problemów decyzyjnych. Problemy decyzyjne to takie, na które program komputerowy musi dać odpowiedź tak lub nie. Deterministyczna maszyna
Turinga odpowiada w sensie teoretycznym zwykłemu komputerowi. Natomiast niedeterministyczna maszyna Turinga to taka, która potrafi w trakcie obliczeń podejmować równoległe rozważanie różnych hipotez. Jeśli np. rozwiązywałaby zagadkę logiczną polegającą na podstawianiu cyfr za rysunki to dochodząc do rysunku bez ustalonego podstawienia mogłaby przyjąć, że i oddzielnie rozważyć podstawienie na rysunek każdej z dziesięciu cyfr. W artykule dowiedziono, że rozwiązywanie problemu na niedeterministycznej maszynie Turinga może być „zredukowane” do dowodzenia twierdzeń w rachunku zdań Boolea. Przez „redukcję” autor rozumie, że mając już gotowe rozwiązanie można zdecydować w czasie wielomianowym na deterministycznej maszynie turinga
czy jest ono poprawne. Podobnie wykazano, że problem wykazania czy jeden z grafów jest izomorficzny z podgrafem drugiego też daje się zredukować do dowodzenia twierdzeń. W artykule tym podano jeszcze kilka problemów o podobnych własnościach. Artykuł ten znalazł wyjście z nierozstrzygniętego do dzisiaj pytania czy omawiane problemy dadzą się rozwiązać na deterministycznej maszynie turinga w czasie wielomianowym czy wymagają już czasu wykładniczego. Cook sprowadził pytania o każdy z tych problemów z osobna do pytania czy którykolwiek znajdzie się po jednej bądź po drugiej stronie, bo to przez wykazane przekształcenia wykaże złożoność całej reszty. Wieloletnie poszukiwania teoretyczne i doświadczalne pokazują, że raczej nie ma szans na szybki algorytm rozwiązujący te problemy(tj.w czasie wielomianowym) ale nikomu jeszcze tego nie udało się udowodnić.
Więcej streszczeń na temat Złożoność obliczeniowa procedur dowodzenia twierdzeń