DAA - Teorema di Cook
Stephen Cook ha presentato quattro teoremi nel suo articolo "The Complexity of Theorem Proving Procedures". Questi teoremi sono indicati di seguito. Comprendiamo che in questo capitolo vengono utilizzati molti termini sconosciuti, ma non abbiamo alcuno scopo per discutere tutto in dettaglio.
Di seguito sono riportati i quattro teoremi di Stephen Cook:
Teorema-1
Se un set S di stringhe è accettato da qualche macchina di Turing non deterministica entro un tempo polinomiale, quindi S è P-riducibile a {DNF tautologies}.
Teorema-2
I seguenti insiemi sono P-riducibili tra loro in coppia (e quindi ognuno ha lo stesso grado di difficoltà polinomiale): {tautologies}, {DNF tautologies}, D3, {sub-graph pair}.
Teorema-3
Per ogni TQ(k) di tipo Q, $ \ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}} $ non ha limiti
C'è un TQ(k) di tipo Q tale che $ T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2} $
Teorema-4
Se l'insieme S di stringhe viene accettato da una macchina non deterministica entro il tempo T(n) = 2n, e se TQ(k) è una funzione di tipo onesta (ovvero numerabile in tempo reale) Q, allora c'è una costante K, così S può essere riconosciuto da una macchina deterministica nel tempo TQ(K8n).
In primo luogo, ha sottolineato il significato della riducibilità del tempo polinomiale. Significa che se abbiamo una riduzione del tempo polinomiale da un problema a un altro, questo assicura che qualsiasi algoritmo temporale polinomiale del secondo problema possa essere convertito in un algoritmo temporale polinomiale corrispondente per il primo problema.
In secondo luogo, ha focalizzato l'attenzione sulla classe NP dei problemi decisionali che possono essere risolti in tempo polinomiale da un computer non deterministico. La maggior parte dei problemi intrattabili appartengono a questa classe, NP.
Terzo, ha dimostrato che un particolare problema in NP ha la proprietà che ogni altro problema in NP può essere ridotto polinomialmente ad esso. Se il problema di soddisfacibilità può essere risolto con un algoritmo temporale polinomiale, allora ogni problema in NP può essere risolto anche in tempo polinomiale. Se un problema in NP è intrattabile, il problema di soddisfacibilità deve essere intrattabile. Pertanto, il problema della soddisfacibilità è il problema più difficile in NP.
Quarto, Cook ha suggerito che altri problemi in NP potrebbero condividere con il problema di soddisfacibilità questa proprietà di essere il membro più difficile di NP.