Cálculos deterministas versus no deterministas

Para entender la clase P y NP, primero debemos conocer el modelo computacional. Por lo tanto, en este capítulo discutiremos dos modelos computacionales importantes.

Computación determinista y la clase P

Máquina de Turing determinista

Uno de estos modelos es la máquina Turing determinista de una sola cinta. Esta máquina consta de un control de estado finito, un cabezal de lectura-escritura y una cinta de dos vías con secuencia infinita.

A continuación se muestra el diagrama esquemático de una máquina de Turing determinista de una cinta.

Un programa para una máquina de Turing determinista especifica la siguiente información:

  • Un conjunto finito de símbolos de cinta (símbolos de entrada y un símbolo en blanco)
  • Un conjunto finito de estados
  • Una función de transición

En el análisis algorítmico, si un problema se puede resolver en tiempo polinomial mediante una máquina de Turing determinista de una cinta, el problema pertenece a la clase P.

Computación no determinista y la clase NP

Máquina de Turing no determinista

Para resolver el problema computacional, otro modelo es la Máquina de Turing no determinista (NDTM). La estructura de NDTM es similar a DTM, sin embargo, aquí tenemos un módulo adicional conocido como módulo de adivinación, que está asociado con un cabezal de solo escritura.

A continuación se muestra el diagrama esquemático.

Si el problema se puede resolver en tiempo polinomial mediante una máquina de Turing no determinista, el problema pertenece a la clase NP.