¿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

Este fenómeno se extiende más allá del problema del viajante de comercio, e incluso más allá de NP, ya que hay incluso algunos indecidible problemas con la característica de que la mayoría de los casos pueden resolverse muy rápidamente.

Existe un subcampo emergente de la teoría de la complejidad llamado complejidad del caso genérico que se ocupa de los problemas de decisión en el caso genérico, el problema de resolver la mayoría o casi todas las instancias de un problema dado. Esto contrasta con la situación en la teoría clásica de la complejidad, donde es en efecto la complejidad del peor caso la que impulsa muchas clasificaciones de complejidad. (E incluso para soluciones aproximadas en problemas NP-duros, el fenómeno del peor caso sigue presente).

Especialmente interesante es el agujero negro fenómeno por el cual la dificultad de un problema no factible o incluso indecidible se concentra en una región muy diminuta, fuera de la cual es fácil. (Aquí, diminuto significa diminuto con respecto a alguna medida natural, como la densidad asintótica). Por ejemplo, muchos de los problemas de decisión clásicos de la teoría combinatoria de grupos, como el problema de la palabra y el problema de la conjugación, pueden resolverse en tiempo lineal en el caso genérico. Este fenómeno proporciona una respuesta negativa al análogo de su pregunta 1 para estos problemas. El hecho de que los problemas se resuelvan fácilmente fuera del agujero negro proporciona una respuesta negativa al análogo de la pregunta 2. Y creo que el hecho de que estos problemas sean realmente indecidibles como problemas totales sugiere que esta forma de resolver casi todos los casos de un problema no nos ayudará con P vs. NP, en tu pregunta 3.

Para la pregunta 4, permítanme mencionar que una versión extrema del fenómeno del agujero negro se da incluso en el problema de detención clásico. Por supuesto, éste es el más famoso de los problemas indecidibles. Sin embargo, Alexei Miasnikov y yo demostramos que para uno de los modelos estándar de máquina de Turing con una cinta infinita unidireccional, existe un algoritmo que resuelve el problema de detención en un conjunto de medida asintótica uno. Es decir, existe un conjunto A de programas de máquinas de Turing, tal que (1) casi todos los programas están en A, en el sentido de la densidad asintótica, (2) A es decidible en tiempo lineal, y (3) el problema de detención es decidible en tiempo lineal para los programas en A. Este resultado aparece en (J. D. Hamkins y A. Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Formal Logic 47, 2006. http://arxiv.org/abs/math/0504351 ). Dentro del agujero negro, el complemento de A, por supuesto, el problema es intratable. La prueba, por desgracia, no se generaliza completamente a todas las demás implementaciones de las máquinas de Turing, ya que para otros modelos se encuentra un agujero negro de alguna medida intermedia entre 0 y 1, en lugar de la medida 0.

Answer 2

Hmm, no es un problema NP-completo, pero espero que siga siendo relevante para (4) y para una pregunta que creo que está implícita en (2).

Es bien sabido que la programación lineal está en P, pero en la práctica el algoritmo simplex (que es exponencial en el peor de los casos) suele ser el método más rápido para resolver problemas de LP, y prácticamente siempre es competitivo con los métodos de punto interior de tiempo polinomial. Sin embargo, el muestreo uniforme de un espacio de problemas es un modelo poco realista, por lo que el análisis del caso medio no resulta convincente. Spielman y Tang introdujeron la noción de "análisis suavizado" para remediarlo, y demostraron que el algoritmo simplex tiene una complejidad de tiempo polinómica suavizada. Echando un vistazo a la página de Spielman, parece que esto se ha aplicado al problema de la mochila, aunque el enlace al artículo está roto.

Re (1): ¿Qué quiere decir con "pequeño"? :) Sospecho que la heurística no ayudaría mucho si se tomara una instancia aleatoria de, digamos, 3SAT con el número correcto de cláusulas y variables, y se redujera a una instancia de TSP. Pero se obtendría una ampliación de tamaño polinómico, así que...

Re (3): Es correcto que la existencia de tal algoritmo, por sí mismo, no implicaría ni P = NP ni P != NP. Pero para "consideraciones prácticas" podría ser enormemente importante, dependiendo de cuáles fueran las constantes, y sin duda estimularía la investigación sobre si existe un algoritmo polinómico en el peor de los casos en la misma línea.

ETA: En realidad, aquí hay una construcción para un problema NP-completo y un algoritmo que incondicionalmente se ejecuta en tiempo polinómico medio. El problema es la unión de un lenguaje en P y un lenguaje NP-completo (resoluble en tiempo exp(n)), tal que el número de instancias de tamaño n del primer problema es algo así como exp(n^3), mientras que el número de instancias del segundo problema es exp(n).

Así que lo interesante de (3) es qué la existencia de un algoritmo polinómico de caso medio para cada problema en NP nos diría. Y ahí la respuesta sigue siendo "nada", pero es concebible que podamos demostrar que P = NP bajo este supuesto.

Por cierto, Impagliazzo habla de algunas de estas cuestiones (aunque no de todas; el artículo tiene 15 años y es anterior a Spielman-Tang, por ejemplo) en quizás el mejor estudio jamás escrito . Lo recomiendo encarecidamente.

Answer 3

Otro enfoque de los problemas NP-completos es lo que se ha dado en llamar complejidad parametrizada.

La idea es que un problema puede ser "difícil" cuando se expresa en términos del tamaño de la entrada, pero se puede reformular el problema con un parámetro k de modo que el problema sea polinómico en términos del tamaño de la entrada, pero exponencial en términos del parámetro k. En algunas situaciones, esto permite encontrar algoritmos que son "manejables" para valores pequeños de k.

http://en.wikipedia.org/wiki/Parameterized_complexity

http://fpt.wikidot.com/

Answer 4

Re: 1), los problemas NP-completos suelen mostrar una transición de fase en complejidad computacional. Véase R. Monasson, et al., "Determining computational complexity from characteristic `phase transitions'". Naturaleza 400 , 133 (1999) (disponible casi al final de la página en http://www.math.ucla.edu/~percus/Enseñanza/RIPS/refs.html ) y también la respuesta a 3). Elegir problemas en los límites de fase o muy cerca de ellos funciona. En el caso del TSP, creo que lo que se conseguiría sería tener muchas distancias por pares muy similares entre un subconjunto de ciudades.

Re: 2), no me atrevo. Véanse las demás referencias en esta respuesta.

Re: 3), la respuesta creo que dependería de la naturaleza característica de los casos de problemas fáciles y difíciles. Susan Coppersmith ha estudiado este tipo de cosas en el contexto del grupo de renormalización para formular una conjetura con sabor a física sobre la cuestión P/NP. Véase http://arxiv.org/abs/cs/0608053

Re: 4), dudo que se pueda decir mucho en estos momentos. Por ejemplo, existen muy buenos solucionadores SAT, capaces de abordar (al menos) miles de variables y cientos de miles de cláusulas. Véase http://www.satcompetition.org/

Answer 5

Gurevich y Shelah demuestran que el problema del camino hamitoniano tiene una complejidad media de casos lineal con respecto al modelo de grafos aleatorios de Erdos http://research.microsoft.com/en-us/um/people/gurevich/opera/71.pdf