DAA - twierdzenie Cooka
Stephen Cook przedstawił cztery twierdzenia w swoim artykule „The Complexity of Theorem Proving Procedures”. Te twierdzenia przedstawiono poniżej. Rozumiemy, że w tym rozdziale użyto wielu nieznanych terminów, ale nie mamy możliwości omówienia wszystkiego szczegółowo.
Oto cztery twierdzenia Stephena Cooka:
Twierdzenie 1
Jeśli zestaw S ciągów jest więc akceptowana przez jakąś niedeterministyczną maszynę Turinga w czasie wielomianowym S jest P-redukowalna do {tautologii DNF}.
Twierdzenie-2
Następujące zbiory są P-redukowalne do siebie w parach (a zatem każdy ma ten sam wielomianowy stopień trudności): {tautologies}, {DNF tautologies}, D3, {sub-graph pairs}.
Twierdzenie-3
Dla każdego TQ(k) typu Q, $ \ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}} $ jest nieograniczone
Tam jest TQ(k) typu Q takie, że $ T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2} $
Twierdzenie-4
Jeśli zbiór S ciągów zostanie zaakceptowany przez niedeterministyczną maszynę w czasie T(n) = 2n, i jeśli TQ(k) jest uczciwą (tj. policzalną w czasie rzeczywistym) funkcją typu Q, to jest stała K, więc S może być rozpoznany przez deterministyczną maszynę w czasie TQ(K8n).
Po pierwsze, podkreślił znaczenie redukowalności wielomianu w czasie. Oznacza to, że jeśli mamy redukcję czasu wielomianu z jednego problemu do drugiego, zapewnia to, że dowolny algorytm czasu wielomianowego z drugiego problemu można przekształcić w odpowiadający algorytm czasu wielomianu dla pierwszego problemu.
Po drugie, zwrócił uwagę na klasę NP problemów decyzyjnych, które mogą być rozwiązane w czasie wielomianowym przez niedeterministyczny komputer. Większość trudnych do rozwiązania problemów należy do tej klasy NP.
Po trzecie, udowodnił, że jeden konkretny problem w NP ma tę właściwość, że każdy inny problem w NP można zredukować do niej wielomianowo. Jeśli problem spełnialności można rozwiązać za pomocą algorytmu wielomianowego czasu, to każdy problem w NP można rozwiązać również w czasie wielomianowym. Jeśli jakikolwiek problem w NP jest nie do rozwiązania, to problem spełnialności musi być nie do rozwiązania. Zatem problem spełnialności jest najtrudniejszym problemem w NP.
Po czwarte, Cook zasugerował, że inne problemy w NP mogą dzielić z problemem spełnialności tę właściwość, że jest najtrudniejszym członkiem NP.