Optmizacion

Estamos de Regreso!!!!!

Despues de unas cortas y bien merecidas vacaciones, es hora de continuar con las entradas. En estos momentos estoy llevando la materia de "topicos selectos de optimizacion" mejor conocida como "opti-2" y como primera tarea es escoger un problema de complejidad NP he decidido hacer esta entrada de introducción "Complejidad computacional: NP-completos", para desvancer las dudas. Espero y les sirva como a mi.

Complejidad computacional: NP

La importancia de esta clase de problemas de decisión es que contiene muchos problemas de búsqueda y de optimización para los que se desea saber si existe una cierta solución o si existe una mejor solución que las conocidas. En esta clase están el problema del viajante (también llamado "problema del agente de ventas" o "problema del agente viajero") donde se quiere saber si existe una ruta óptima que pasa por todos los nodos en un cierto grafo y el problema de satisfacibilidad booleana en donde se desea saber si una cierta fórmula de lógica proposicional puede ser cierta para algún conjunto de valores booleanos para las variables.

Dada su importancia, se han hecho muchos esfuerzos para encontrar algoritmos que decidan algún problema de NP en tiempo polinómico. Sin embargo, pareciera que para algunos problemas de NP (los del conjunto NP-completo) no es posible encontrar un algoritmo mejor que simplemente realizar una búsqueda exhaustiva.

Relación con otras clases de complejidad

NP contiene todos los problemas pertenecientes a las clases P y NP-C, y a su vez está contenido en el conjunto de los PSPACE. Aún se desconoce si estas inclusiones son estrictas o no, y si la intersección entre los NP y Co-NP es o no vacía.

En particular, el mayor problema en ciencias de la computación consiste en responder al siguiente problema de decisión: ¿P=NP?

Ahora, nuestra tarea consta en escoger un problema NP-completo. Pero como es en equipo, estamos a la espera de los demas integrantes para poder escoger el problema.

Entonces que es NP-completo?


NP-completo es el subconjunto de los problemas de decisión 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 muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico.


Ejemplos de problemas NP-Completos


Existe una lista de 21 Problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos, y que cumplen la característica en común de que todos ellos pertenecen a la clase de complejidad de los NP-completos. Esta lista fue elaborada en 1972 por el informático teórico Richard Karp, en su trabajo seminal "Reducibility Among Combinatorial Problems" (Reducibilidad entre Problemas Combinatorios), como profundización del trabajo de Stephen Cook, quien en 1971 había demostrado uno de los resultados más importantes y pioneros de la complejidad computacional: la NP-completitud del Problema de satisfacibilidad boole.

• SAT (Problema de satisfacibilidad booleana, para fórmulas en forma normal conjuntiva)
  • 0-1 INTEGER PROGRAMMING (Problema de la Programación lineal entera)
  • CLIQUE (Problema del clique, véase también Problema del conjunto independiente)
    • SET PACKING (Problema del empaquetamiento de conjuntos)
    • VERTEX COVER (Problema de la cobertura de vértices)
      • SET COVERING (Problema del conjunto de cobertura)
      • FEEDBACK NODE SET
      • FEEDBACK ARC SET
      • DIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano dirigido)
        • UNDIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano no dirigido)
  • 3-SAT (Problema de satisfacibilidad booleana de 3 variables por cláusula)
    • CHROMATIC NUMBER (Problema de la coloración de grafos)
      • CLIQUE COVER (Problema de la cobertura de cliques)
      • EXACT COVER (Problema de la cobertura exacta)
        • HITTING SET
        • STEINER TREE
        • 3-DIMENSIONAL MATCHING (Problema del matching tridimensional)
        • KNAPSACK (Problema de la mochila)
          • JOB SEQUENCING (Problema de las secuencias de trabajo)
          • PARTITION (Problema de la partición)
            • MAX-CUT (Problema del corte máximo)

Tras un tiempo se descubrió que muchos de estos problemas podían ser resueltos si su enunciado se particularizaba a unas ciertas clases, o podían ser resueltos aproximadamente con un error máximo de un cierto porcentaje. Sin embargo David Zuckerman demostró en 1996 que cada uno de estos 21 problemas tiene una versión restringida de optimización que es no aproximable a menos que P = NP, demostrando que la versión de la reducción, dada por Karp, generaliza un tipo específico de reducción por aproximación.

Soluciones Aproximadas

Actualmente, todos los algoritmos conocidos para problemas NP-completos utilizan tiempo exponencial con respecto al tamaño de la entrada. Se desconoce si hay algoritmos más rápidos, por lo cual, para resolver un problema NP-completo de tamaño arbitrario, se utiliza uno de los siguientes enfoques:

• 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 todos los problemas NP-completos tienen algoritmos de aproximación.
• Probabilístico: Un algoritmo probabilístico utiliza aleatoriedad para obtener en promedio una buena solución al problema planteado con una pequeña probabilidad de fallar, para una distribución de los datos de entrada dada.
• Restricciones: Restringiendo la estructura de las entradas se pueden encontrar algoritmos más rápidos.
• Casos particulares: Puede ocurrir que se reconozcan casos particulares del problema para los cuales existen soluciones rápidas.
• Algoritmo genético: Algoritmos que mejoran las posibles soluciones hasta encontrar una que posiblemente esté cerca del óptimo. Tampoco existe forma de garantizar la calidad de la respuesta.
• Heurísticas: Un algoritmo que trabaja razonablemente bien en muchos casos. En general son rápidos, pero no existe medida de la calidad de la respuesta. Las aproximaciones metaheurísticas suelen ser empleadas.