Problemas NP-Completos (Parte I)

Eres de computación, vas saliendo de una conferencia, coloquio, clase magistral... Y escuchas al tipo que va hablando con la voz más alta posible para que todos puedan escucharlo

- ¡Oh sí! NP, NP-hard, Heurísticas, Algoritmos Probabilísticos bla bla bla...

🙄

Ni la cultura ni el conocimiento debería ser privilegio de clase o motivo de ego, ok?

 

Un problema que es NP-completo es una llave muy importante dentro de la computación ya que resolver un problema de este tipo significaría obtener en automático la solución para otra gran cantidad de problemas, en realidad una familia de problemas; los problemas NP.

Dicho de otro modo, un problema NP-Completo es aquel que al resolverlo, resuelve todos los problemas de tipo NP.

Pero vamos por pasos.

Máquinas de Turing

Veamos el siguiente diagrama:

 

 

Autómata determinista.

Lo anterior es un autómata  y puede entenderse como una simplificación de una máquina de Turing. 

 

A cada q_i le llamaremos estado. Los estados del autómata anterior son el amarillo y los color melón.

 

Decimos que el autómata acepta a una cadena si al procesarla llega al estado de aceptación qₐ.

 

Decimos que es una versión simplificada de las MT porque se omite una cinta infinita y un cabezal que puede escribir en dicha cinta¹.

 

La forma en que el autómata procesa a una cadena es:

1. Posicionarse en el estado inicial q₀

2. Posicionarse en el primer caracter del input

3. Movernos al estado indicado de acuerdo al caracter en que se esté parado

4. Si llegamos a qₐ detenernos, el autómata ha aceptado.

4. Si no, avanzar un caracter en el input, si ya no quedan caracteres en el input, el autómata a ha rechazado.

5. Volver al paso 3

 

Veamos que el autómata anterior acepta al input "ana", ya que iniciando en q₀, podemos alcanzar el estado de aceptación qₐ.

 

El autómata anterior es determinista, ya que no hay ambigüedad de hacia dónde moverse en cada paso, al contrario del que veremos a continuación.

 

 

Autómata no determinista.

 

Notemos que si en este autómata quisiéramos empezar a procesar la cadena "ana" habría ambigüedad ya que en el primer paso sería posible movernos al estado q₁, q₃ o q₄.

 

Este autómata no determinista puede ser entendido como una simplificación de las máquinas no deterministas de Turing¹.

 

Ante la ambigüedad de camino, el modelo teórico no determinista puede ser visto de cualquiera de las siguientes maneras:

 

1. El autómata decide qué camino tomar y siempre toma el camino correcto.

2. El autómata prueba todos los caminos posibles y, si existe, se queda sólo con aquel camino que lleve al estado de aceptación.

Así, en el ejemplo anterior, si lo viéramos desde la primera perspectiva, tendríamos que el autómata decide seguir por el camino que lleva a q₁, ya que es el único que lleva a qₐ, el estado de aceptación.

 

Utilizando la segunda perspectiva, tendríamos que el autómata prueba todos los posibles caminos y se queda sólo con aquel que lleva a qₐ.

 

Entonces...

Ya tenemos parcialmente a las máquinas deterministas de Turing y las máquinas no deterministas de Turing.

Las máquinas deterministas son aquellas donde existe un sólo camino posible para cada cambio de estado.

Las máquinas no deterministas son aquellas donde existen varios caminos posibles a tomar y la máquina siempre decide el camino correcto si es que existe.

La tesis de Chuch-Turing afirma que es posible abstraer cualquier algoritmo a una máquina de este tipo. Claro, es imposible dar una demostración para esta afirmación, pero funciona bastante bien con la noción de algoritmo que se ha construido.

Hasta ahora la tesis Church-Turing es más bien un enunciado que se ha mantenido cierto porque no se ha encontrado un contrajemplo, pero que es ampliamente aceptado.

Tiempo de Ejecución

Al igual que un programa de computadora, cada MT toma cierto tiempo en ejecutarse, y al igual que un programa de computadora el tiempo de ejecución de estás máquinas, generalmente es medida con funciones.

 

Por ejemplo si  x es el tamaño del input

 

f(x) = x²

g(x) = e^x

ˣ Subíndices y superíndices Unicode - https://es.qaz.wiki/wiki/Unicode_subscripts_and_superscripts

ˣ Subíndices y superíndices Unicode - https://es.qaz.wiki/wiki/Unicode_subscripts_and_superscripts

ˣ Subíndices y superíndices Unicode - https://es.qaz.wiki/wiki/Unicode_subscripts_and_superscripts

ˣ Subíndices y superíndices Unicode - https://es.qaz.wiki/wiki/Unicode_subscripts_and_superscripts

 

La función denota que si el tamaño del input es x, entonces el tiempo que le tomaría a la MT en terminar es x² y e^x , respectivamente.

NP

Son las iniciales de Non-deterministic Polinomial.

Este es un conjunto, que contiene a todos los problemas de decisión (aquellos donde la respuesta sólo es Sí o No) que pueden resolverse con una  máquina de Turing no determinista y que además su tiempo de ejecución está determinado por un polinomio.

 

 

En suma...

Los problemas NP son curiosos porque trabajan bajo un modelo de cómputo extraño. De verdad me he preguntado ¿por qué se decidió seguir construyendo sobre el modelo no determinista de Turing?²

 

La cosa es que estamos esperando encontrar una forma de programar "suerte" o algoritmos que sean "suertudos", para que siempre usen al camino correcto sin necesidad de usar memoria o tiempo exponencial.

Hay formas de encontrar el "mejor" camino posible (Heurísticas) y los resultados de esos métodos a veces son suficientemente buenos, pero esa no es la idea detrás de las máquinas no deterministas.

La idea es tener un algo (un ente, un ser, otro modelo de cómputo, inteligencia, suerte, un oráculo) que, para cualquier problema, sepa qué camino tomar para llegar al estado de aceptación. 

 

Pero desafortunadamente la Inteligencia Artificial con la que se cuenta hasta ahora, está muy lejos de ser inteligente, por este y otros motivos está muy lejos de ser viable para resolver este problema.

 

Sobre este hueco teórico descansa el problema P vs NP, del cual hablaré en post venideros.

Continuará...

Siguiente post: 3-SAT es NP-Completo y su demostración.

Instagram (alerta nuevo post): https://www.instagram.com/mathandcss/

 

¹Para que fuera una máquina de Turing tendríamos que describir: Con movimiento del cabezal por default a la derecha, escribiendo el mismo símbolo en la cinta a cada paso, cualquier transición no descrita lleva en automático a un estado de rechazo. (No es vital entender esta nota)

²Aunque las máquinas de Turing no deterministas y las deterministas son equivalentes, la idea detrás del no determinismo es evitar usar memoria y/o tiempo exponencial.

**El post debe entenderse como una explicación informal, parcial y que omite muchos detalles con fines informativos.**

Bibliografía

- M. Sipser, (2021), Introduction to the Theory of Computation (3rd ed), Cenage Learning, Inc.