You are currently browsing the tag archive for the ‘NP-completo’ tag.

Un problema puede ser más o menos difícil de resolver. La complejidad computacional pretende clasificar los problemas computacionales desde el punto de vista de cuanto cuesta resolverlos. Y para cuantificar esta dificultad de una manera teórica y objetiva, lo que se hace es ver como varia el tiempo de resolución con el tamaño de la entrada.

De esta manera, un problema perteneciente a la clase P, un problema resoluble en tiempo polinómico, es un problema cuyo tiempo de resolución es una función polinómica del tamaño de la entrada (si crece poco el tamaño de la entrada, crece poco el tiempo que tardamos en resolverlo, lo cual hace que estos problemas sean tratables).

¿Y qué quiere decir que un problema es de clase NP? Son aquellos problemas para los que es difícil encontrar una solución pero fácil verificarla, es decir, no se conoce ningún algoritmo polinómico que nos encuentre una solución pero si lo existe para comprobar que efectivamente lo es.

Para aclarar la definición anterior, pongamos un ejemplo: el problema del viajante de comercio. Dado un conjunto de ciudades, encontrar una ruta para un comerciante de manera que pase por TODAS las ciudades UNA ÚNICA vez. Este problema se traduce en encontrar un ciclo Hamiltoniano en un grafo. Un crecimiento moderado en el número de ciudades implicadas hace que el problema se vuelva prácticamente intratable. Sin embargo, si nos dan ya una solución, una ruta, es prácticamente trivial comprobar si es un ciclo hamiltoniano o no.

El problema P vs NP pretende demostrar si estos dos conjuntos son o no el mismo.

Dos definiciones complementarias para terminar.

  • Un problema es NP-completo si es un problema NP de los mas difíciles, dejémoslo ahí. El problema anterior es un problema de esta clase. Una propiedad que tienen estos problemas es que son todos equivalentes, desde el punto de vista de complejidad computacional, entre si, es decir, existe un algoritmo que traduce cualquier problema NP-completo en cualquier otro en tiempo polinómico. De manera que, si lográramos un algoritmo en P que resolviera uno de ellos, tendríamos un algoritmo en P para todos ellos (traducimos el otro problema al primero en tiempo polinómico, lo resolvemos en tiempo polinómico y traducimos la solución a una solución del original en tiempo polinómico).
  • Un problema es NP-duro si es, al menos, tan difícil como NP.

 

 

agosto 2017
L M X J V S D
« Jul    
 123456
78910111213
14151617181920
21222324252627
28293031