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.