¿Resolver problemas NP en tiempo (normalmente) polinómico?

Question

Que un problema sea NP-completo no significa que no pueda resolverse rápidamente.

El mejor ejemplo de esto es probablemente el problema del viajante de comercio, para el que se han resuelto de forma óptima instancias extraordinariamente grandes utilizando heurísticos avanzados, por ejemplo sofisticadas variaciones de bifurcación . El tamaño de los problemas que pueden resolverse exactamente con estas heurísticas es alucinante, en comparación con el tamaño que uno predeciría ingenuamente a partir del hecho de que el problema es NP. Por ejemplo, se ha resuelto un recorrido por las 25.000 ciudades de Suecia, así como un VLSI de 85900 puntos (véase aquí para obtener información sobre ambos).

Ahora tengo algunas preguntas:

1) ¿Existen casos especiales de tamaño razonablemente pequeño en los que estas heurísticas no puedan encontrar el recorrido óptimo o lo hagan con extrema lentitud?

2) En el caso medio (de puntos distribuidos uniformemente, digamos), ¿se sabe si el tiempo para encontrar el recorrido óptimo utilizando estas heurísticas es asintóticamente exponencial n, a pesar del éxito en la resolución de casos sorprendentemente grandes? ¿O es asintóticamente polinómico, o es un análisis demasiado difícil de realizar?

3) ¿Es correcto decir que la existencia de un algoritmo polinómico en el caso medio y exponencial en el caso peor para resolver problemas NP no tiene importancia para P=NP?

4) ¿Qué puede decirse de la estructura de los problemas que permiten resolver casos sorprendentemente grandes con exactitud mediante métodos heurísticos frente a los que no?

Answer 1

Su mensaje parece suponer algo así como $\mathsf{P} \neq \mathsf{NP}$ y que un $\mathsf{NP\text{-}complete}$ problema es difícil de resolver, al menos en teoría. Como probablemente sepas, aunque los expertos lo creen ampliamente, se desconoce.

Pero asumamos una forma más fuerte de $\mathsf{NP}\neq\mathsf{P}$ por ejemplo ETH . La prueba SAT es una de las más estudiadas $\mathsf {NP\text{-}complete}$ (si no el que más), y hay reducciones fáciles de SAT a TSP y viceversa. Así que voy a utilizar SAT para responder a sus preguntas, cosas similares se aplican a TSP (por ejemplo, si usted tiene una pequeña instancia difícil de SAT entonces usted puede convertirlo en una pequeña instancia difícil de TSP).

Normalmente, los casos a los que nos enfrentamos en la práctica tienen bastante más estructura que un caso arbitrario del problema. Por ello, los investigadores pueden diseñar algoritmos que exploten estas estructuras. Existen algoritmos industriales de resolución de SAT que se utilizan para resolver instancias enormes de SAT (con varios cientos de miles de variables) en la práctica. Por otro lado, sabemos que todos estos solucionadores SAT rinden exponencialmente mal en fórmulas naturales, simples y pequeñas como PHP (el principio del encasillamiento).

Existen estructuras similares en los problemas TSP, por ejemplo, el grafo del mapa de Suecia que has mencionado es un grafo plano, y muchos problemas de grafos se simplifican mucho cuando la entrada se restringe a grafos planos. Por lo tanto, si las instancias del TSP que te interesan en la práctica son un subconjunto de todos los grafos, entonces se trata de un problema diferente al TSP original y es posible que el problema restringido no sea $\mathsf{NP\text{-}hard}$ más. (Para algunos problemas de grafos que resultan más fáciles en casos restringidos, véase esta pregunta .)

1. Sí, hay casos de problemas pequeños para los que los algoritmos utilizados en la práctica para resolver casos enormes no consiguen resolver estos casos de problemas pequeños en un tiempo razonable, por ejemplo, PHP para SAT.

2. Muchos creen que es así, pero no disponemos de límites inferiores de tiempo exponencial incondicional para el tiempo de ejecución de los algoritmos (generales) que resuelven estos problemas.

3. Si lo he entendido bien, está preguntando algo así como si $TSP \in$ $\mathsf{AveP}$ implica $\mathsf{NP} = \mathsf{P}$ ? Que yo sepa, se desconoce.

4. No estoy seguro de a qué te refieres con resolver utilizando métodos heurísticos, pero si te refieres a $\mathsf{HeurP}$ y desea compararlo con $\mathsf{P}$ entonces debemos tener cuidado, ya que los problemas de estas clases son de distinto tipo. Si te refieres al problema de decisión original más la distribución uniforme, entonces el Zoo no dice mucho y la respuesta es probablemente desconocida.

Answer 2

Creo que las demás respuestas han respondido a la mayoría de sus preguntas, pero hay algunos hechos relevantes que no se han mencionado explícitamente.

En cuanto a la pregunta 1, ciertamente se pueden crear instancias razonablemente pequeñas que hagan que los métodos heurísticos tarden mucho tiempo. Ser NP-completo significa que se puede reducir cualquier otro problema en NP a él, por lo que basta con tomar una instancia difícil de algún otro problema (factorización de un gran módulo RSA, por ejemplo), y reducirlo a TSP (o su favorito "fácil" problema NP-completo).

En cuanto a la pregunta 2, tienes razón en que los programas más avanzados, como CPLEX, utilizan heurísticas muy sofisticadas que (probablemente) no pueden analizarse con rigor. Sin embargo, ha habido algún éxito en este sentido; un estudio relativamente documento reciente de Frieze y Pegden muestra que una serie de heurísticas TSP simples no pueden encontrar soluciones aproximadas asintóticamente óptimas a instancias TSP euclidianas aleatorias. Se trata de un resultado bastante notable, ya que existen esquemas de aproximación en tiempo lineal para el TSP euclidiano.

En cuanto a la pregunta 3, la forma habitual de formalizar tu hipótesis de un algoritmo politímico de caso medio para un problema NP-duro es la inclusión $\textsf{DistNP}\subseteq \textsf{AvgP}$ . Impagliazzo ha construyó un oráculo con respecto a la cual $\textsf{DistNP}\subseteq \textsf{AvgP}$ pero $\textsf{NP} \subsetneq \textsf{BPP}$ . En otras palabras, cualquier argumento que de alguna manera deduzca que $\textsf{P}=\textsf{NP}$ a partir del supuesto de que $\textsf{DistNP}\subseteq \textsf{AvgP}$ debe fallar al relativizar y, por tanto, ser muy sutil. (En particular, como cabría esperar, no sabemos cómo demostrar tal implicación).

En cuanto a la pregunta 4, se trata de una cuestión fascinante para la que actualmente no se conoce una respuesta plenamente satisfactoria. En algunos casos concretos, se puede dar algún tipo de explicación. Por ejemplo, en el caso de k-SAT, las conexiones con la física estadística permiten explicar por qué algoritmos inspirados en la física como propagación de encuestas son tan eficaces para "la mayoría" de los casos. O a veces se puede demostrar que un problema es trazable de parámetro fijo o tiene un esquema de aproximación en tiempo polinómico, y a la inversa a veces se puede demostrar que esta no puede ser cierto a menos que alguna suposición estándar como $\textsf{P}\ne\textsf{NP}$ es violada. Sin embargo, estamos lejos de poder explicar teóricamente en general por qué algunos problemas NP-duros son fáciles en la práctica y otros no.