Si Piensas Que La Vida Se Rige Por La Razon La Posibilidad De Vivir Queda Destruida

Problemas NP


1 Definiciones


1 La clase P


Un algoritmo se dice polinomialmente acotado si la complejidad de su peor caso está acotada por una función polinomial del tamaño de la entrada, es decir, si existe un polinomio p tal que para cada entrada de tamaño n el algoritmo termina a lo sumo en p(n) pasos. Un problema se dice polinomialmente acotado si existe un algoritmopolinomialmente acotado que lo resuelva.


La clase P comprende el tipo de problemas que están polinomialmente acotados.


2 La clase NP


Un problema se encuentra dentro del conjunto NP si, y sólo si, puede resolverse mediante un algoritmo no determinístico en tiempo polinomial. El nombre NP proviene de “nondeterministic polynomial-bounded” (polinomialmente acotado no determinístico)


Unacomputadora no determinística es, de manera informal, aquella que en cualquier paso de sus cálculos puede encontrarse con dos o más cursos alternativos de acción y puede producir copias de sí misma, incluyendo el contenido de su memoria, y continuar con su trabajo de forma independiente para cada alternativa. Considerando otro punto de vista, podemos pensar en un algoritmo no determinístico como aquelque escoge de forma arbitraria uno de los posibles cursos de acción cada vez que se enfrenta con varias posibilidades. La elección puede pensarse como una pregunta que realiza el algoritmo para saber qué alternativa lo conduce a la solución. Empleando esta interpratación de cálculos no determinísticos, decimos que un algoritmo no determinístico resuelve un problema si existe alguna secuencia depreguntas que pueden realizarse para alcanzar una solución. Supongamos, por ejemplo, que el problema es determinar si un grafo dado es k-coloreable. Un algoritmo no determinístico podría comenzar coloreando el primer vértice con un color arbitrario, y luego, en cada paso, colorear un vértice más y verificar que en ese punto ningún vértice adyacente tiene el mismo color asignado. Cada vez que elalgoritmo colorea un nuevo vértice, tiene k opciones.


1 Problemas NP-Completo


En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión[1] en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muyprobablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema de NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico.


2 Soluciones aproximadas


Actualmente, todos los algoritmos conocidos para problemas NP-completos utilizan tiempo exponencial con respecto al tamaño de la entrada. Sedesconoce si hay mejores algoritmos, por la cual, para resolver un problema NP-completo de tamaño arbitrario se utiliza uno de los siguientes enfoques:


1. Aproximación: Un algoritmo que rápidamente encuentra una solución no necesariamente óptima, pero dentro de un cierto rango de error. En algunos casos, encontrar una buena aproximación es suficiente para resolver el problema, pero no todoslos problemas NP-completos tienen buenos algoritmos de aproximación.


2. Probabilístico: Una algoritmo probabilístico obtiene en promedio una buena solución al problema planteado, para una distribución de los datos de entrada dada.


3. Casos particulares: Cuando se reconocen casos particulares del problema para los cuales existen soluciones rápidas.


4. Heurísticas: Unalgoritmo que trabaja razonablemente bien en muchos casos. En general son rápidos, pero no existe medida de la calidad de la respuesta.


Los algoritmos de aproximación no garantizan la mejor solución, pero proporcionan una que es cercana a la óptima. En muchas aplicaciones, una solución aproximada es suficientemente buena, especialmente cuando el tiempo requerido para encontrar la solución óptima...