Computações Determinísticas vs. Não Determinísticas

Para entender a classe P e NP, primeiro devemos conhecer o modelo computacional. Portanto, neste capítulo, discutiremos dois modelos computacionais importantes.

Computação Determinística e a Classe P

Máquina de Turing Determinística

Um desses modelos é a máquina de Turing determinística de uma fita. Esta máquina consiste em um controle de estado finito, um cabeçote de leitura e gravação e uma fita bidirecional com seqüência infinita.

A seguir está o diagrama esquemático de uma máquina de Turing determinística de uma fita.

Um programa para uma máquina de Turing determinística especifica as seguintes informações -

  • Um conjunto finito de símbolos de fita (símbolos de entrada e um símbolo em branco)
  • Um conjunto finito de estados
  • Uma função de transição

Na análise algorítmica, se um problema pode ser resolvido em tempo polinomial por uma máquina de Turing de uma fita determinística, o problema pertence à classe P.

Computação Não Determinística e a Classe NP

Máquina de Turing Não Determinística

Para resolver o problema computacional, outro modelo é a Máquina de Turing Não Determinística (NDTM). A estrutura do NDTM é semelhante ao DTM, porém aqui temos um módulo adicional conhecido como módulo de adivinhação, que está associado a um cabeçote somente de gravação.

A seguir está o diagrama esquemático.

Se o problema pode ser resolvido em tempo polinomial por uma máquina de Turing não determinística, o problema pertence à classe NP.