DAA - Teorema de Cook

Stephen Cook apresentou quatro teoremas em seu artigo “The Complexity of Theorem Proving Procedures”. Esses teoremas são declarados abaixo. Nós entendemos que muitos termos desconhecidos estão sendo usados ​​neste capítulo, mas não temos nenhum escopo para discutir tudo em detalhes.

A seguir estão os quatro teoremas de Stephen Cook -

Teorema-1

Se um conjunto S de strings é aceito por alguma máquina de Turing não determinística dentro do tempo polinomial, então S é P-redutível para {DNF tautologias}.

Teorema-2

Os seguintes conjuntos são P-redutíveis uns aos outros em pares (e, portanto, cada um tem o mesmo grau de dificuldade polinomial): {tautologias}, {DNF tautologias}, D3, {pares de subgráficos}.

Teorema-3

  • Para qualquer TQ(k) do tipo Q, $ \ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}} $ é ilimitado

  • Existe um TQ(k) do tipo Q de modo que $ T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2} $

Teorema-4

Se o conjunto S de strings for aceito por uma máquina não determinística dentro do tempo T(n) = 2n, e se TQ(k) é uma função honesta (ou seja, contagem em tempo real) do tipo Q, então há uma constante K, então S pode ser reconhecido por uma máquina determinística dentro do tempo TQ(K8n).

  • Primeiro, ele enfatizou a importância da redutibilidade do tempo polinomial. Isso significa que se tivermos uma redução de tempo polinomial de um problema para outro, isso garante que qualquer algoritmo de tempo polinomial do segundo problema possa ser convertido em um algoritmo de tempo polinomial correspondente para o primeiro problema.

  • Em segundo lugar, ele focou a atenção na classe NP de problemas de decisão que podem ser resolvidos em tempo polinomial por um computador não determinístico. A maioria dos problemas intratáveis ​​pertence a esta classe, NP.

  • Terceiro, ele provou que um problema particular em NP tem a propriedade de que todos os outros problemas em NP podem ser polinomialmente reduzidos a ele. Se o problema de satisfatibilidade pode ser resolvido com um algoritmo de tempo polinomial, então todo problema em NP também pode ser resolvido em tempo polinomial. Se algum problema em NP for intratável, então o problema de satisfatibilidade deve ser intratável. Assim, o problema de satisfatibilidade é o problema mais difícil em NP.

  • Quarto, Cook sugeriu que outros problemas em NP podem compartilhar com o problema da satisfatibilidade essa propriedade de ser o membro mais difícil de NP.