DAA - Cook'un Teoremi
Stephen Cook, "The Complexity of Theorem Proving Procedures" adlı makalesinde dört teorem sundu. Bu teoremler aşağıda belirtilmiştir. Bu bölümde birçok bilinmeyen terimin kullanıldığını anlıyoruz, ancak her şeyi ayrıntılı olarak tartışmak için herhangi bir kapsamımız yok.
Stephen Cook'un dört teoremi aşağıdadır -
Teorem-1
Eğer bir set S Polinom zaman içinde bazı deterministik olmayan Turing makinesi tarafından kabul edilir, sonra S {DNF tautolojileri} için P-indirgenebilir.
Teorem-2
Aşağıdaki kümeler çiftler halinde birbirlerine P-indirgenebilirdir (ve dolayısıyla her biri aynı polinom zorluk derecesine sahiptir): {tautolojiler}, {DNF tautolojileri}, D3, {alt grafik çiftleri}.
Teorem-3
Herhangi TQ(k) tip Q, $ \ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}} $ sınırsız
Var TQ(k) tip Q öyle ki $ T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2} $
Teorem-4
Dize kümeleri zaman içinde deterministik olmayan bir makine tarafından kabul edilirse T(n) = 2n, ve eğer TQ(k) dürüst (yani gerçek zamanlı sayılabilir) bir tür işlevdir Q, o zaman bir sabit K, yani S zaman içinde deterministik bir makine tarafından tanınabilir TQ(K8n).
İlk olarak, polinom zaman indirgenebilirliğinin önemini vurguladı. Bir problemden diğerine bir polinom zaman indirgememiz varsa, bu, ikinci problemdeki herhangi bir polinom zaman algoritmasının ilk problem için karşılık gelen bir polinom zaman algoritmasına dönüştürülebilmesini sağlar.
İkinci olarak, deterministik olmayan bir bilgisayar tarafından polinom zamanında çözülebilen karar problemlerinin NP sınıfına odaklandı. İnatçı problemlerin çoğu bu sınıfa, NP'ye aittir.
Üçüncüsü, NP'deki belirli bir sorunun NP'deki diğer her sorunun polinomik olarak ona indirgenebileceği özelliğine sahip olduğunu kanıtladı. Tatmin edilebilirlik problemi bir polinom zaman algoritması ile çözülebiliyorsa, NP'deki her problem polinom zamanda da çözülebilir. NP'deki herhangi bir problem çözülemezse, tatmin edici problem çözülemez olmalıdır. Dolayısıyla, tatmin problemi NP'deki en zor problemdir.
Dördüncüsü, Cook, NP'deki diğer sorunların, NP'nin en zor üyesi olma özelliğini tatmin etme sorunu ile paylaşabileceğini öne sürdü.