La programación lineal (LP) está en P y la programación entera (IP) es NP-hard. Pero dado que las computadoras solo pueden manipular números con precisión finita, en la práctica una computadora usa números enteros para la programación lineal. Debido a esto, ¿no deberían LP e IP estar en la misma clase de complejidad?
complexity-theory
polynomial-time
Sasha el novato
fuente
fuente
Respuestas:
No puedo comentar ya que requiere 50 repeticiones, pero hay algunas ideas falsas que se están difundiendo, especialmente el comentario de Raphael "En general, un dominio continuo significa que no hay fuerza bruta (ni heurísticas inteligentes para acelerarlo)".
Esto es absolutamente falso. El punto clave es de hecho convexidad. Salvo algunas calificaciones de restricción técnica, minimizar una función convexa (o maximizar una función cóncava) sobre un conjunto convexo es esencialmente trivial, en el sentido de convergencia de tiempo polinomial.
Hablando en términos generales, se podría decir que existe una correspondencia entre la convexidad de un problema en la optimización "matemática" y la viabilidad de los algoritmos codiciosos en la optimización "informática". Esto es en el sentido de que ambos habilitan métodos de búsqueda local. Nunca tendrá que retroceder en un algoritmo codicioso y nunca tendrá que arrepentirse de una dirección de descenso en un problema de optimización convexa. Las mejoras locales en la función objetivo SIEMPRE lo llevarán más cerca del óptimo global.
Esto no es así en el caso no convexo. Aquí, puede haber un mínimo global, pero varios mínimos locales a los que siempre se atraerá un algoritmo de descenso local, de la misma manera que lo hacen los algoritmos codiciosos cuando se aplican a problemas NP. A veces encuentran el verdadero óptimo, la mayoría de las veces no.
fuente
La respuesta corta: porque puedes usar números enteros para simular booleanos para SAT , pero cuando no te limitas a esto, entonces no puedes simular SAT. Obtendrá una respuesta factible, pero ya no tiene ningún significado en términos de cualquier instancia de SAT que intentara simular.
fuente
La razón por la que la programación lineal es "eficiente" es que el espacio de solución puede estar representado por un solo poliedro convexo. Si uno está tratando de encontrar el vértice "más alto" en ese poliedro (uno puede aplicar una transformación lineal a cualquier problema de programación lineal para hacer que la "altura" se corresponda con la cantidad a maximizar), entonces desde cualquier vértice uno puede viajar a lo largo de los bordes para el punto más alto sin tener que ir "cuesta abajo". Lo que hace que la programación de enteros sea "difícil" es que no hay un espacio de solución continuo, sino que hay muchos espacios de solución disjuntos , y no hay forma de trabajar incrementalmente hacia la solución óptima.
fuente
Las otras respuestas son correctas, pero las encuentro un poco técnicas. Suponga que ha barrido (eliminado) una matriz y está buscando cualquier solución y la matriz se ve así:
fuente