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.