este problema se puede resolver de variadas formas, sin embargo te dejamos la que en nuestra opinión es la solución más completa.
Solución:
Este fenómeno se extiende más allá del problema del viajante de comercio, e incluso más allá de NP, ya que incluso hay algunos indecidible problemas con la función que la mayoría de los casos se pueden resolver muy rápidamente.
Hay 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 de los casos la que impulsa muchas clasificaciones de complejidad. (E incluso para soluciones aproximadas en problemas NP-difíciles, el fenómeno del peor de los casos todavía está presente).
Particularmente interesante es el agujero negro fenómeno, el fenómeno por el cual la dificultad de un problema inviable o incluso indecidible se concentra en una región muy pequeña, 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 de grupos combinatorios, como el problema verbal y el problema de conjugación, son resolubles 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 su pregunta 3.
Para la pregunta 4, permítanme mencionar que una versión extrema del fenómeno del agujero negro es proporcionada incluso por el clásico problema de detención. Por supuesto, este 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, hay un conjunto A de programas de máquina de Turing, tal que (1) casi todos los programas están en A, en el sentido de densidad asintótica, (2) A es decidible en tiempo lineal y (3) el problema de detención es lineal tiempo decidible para programas en A. Este resultado aparece en (JD Hamkins y A. Miasnikov, The halting problem is decidible on a set of asymptotic probabilidad one, Notre Dame J. Formal Logic 47, 2006. http://arxiv.org/ abs/matemáticas/0504351). Dentro del agujero negro, el complemento de A, por supuesto, el problema es intratable. Desafortunadamente, la prueba no se generaliza completamente a todas las demás implementaciones de las máquinas de Turing, ya que para otros modelos uno encuentra un agujero negro de alguna medida intermedia entre 0 y 1, en lugar de medir 0.
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 PL, y prácticamente siempre es competitivo con los métodos de punto interior de tiempo polinomial. Sin embargo, el muestreo uniforme de algún espacio de problemas es un modelo poco realista, por lo que el análisis de casos promedio no es convincente. Spielman y Tang introdujeron la noción de “análisis suavizado” para remediar esto, y demostraron que el algoritmo simplex tiene una complejidad de tiempo polinomial 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 periódico está roto.
Re (1): ¿Qué quieres decir con “pequeño”? 🙂 Sospecho que la heurística no sería de mucha ayuda si tomara una instancia aleatoria de, digamos, 3SAT con el número correcto de cláusulas y variables, y la redujera a una instancia de TSP. Pero obtendrías una explosión del tamaño de un polinomio, así que…
Re (3): Es correcto que la existencia de dicho algoritmo, por sí solo, no implicaría ni P = NP ni P != NP. Pero por “consideraciones prácticas” podría ser muy importante, dependiendo de cuáles fueran las constantes, y sin duda impulsaría la investigación sobre si había un algoritmo polinomial 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 polinomial de caso promedio. El problema es la unión de un lenguaje en P y un lenguaje NP-completo (soluble 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).
Entonces, lo interesante de (3) es la existencia de un algoritmo polinomial de caso promedio para todos problema en NP nos diría. Y ahí la respuesta sigue siendo “nada”, pero es concebible que podamos probar P = NP bajo esta suposición.
Por cierto, Impagliazzo habla sobre algunos de estos temas (aunque no todos; el artículo tiene 15 años y es anterior a Spielman-Tang, por ejemplo) en quizás el mejor artículo de encuesta jamás escrito. Lo recomiendo altamente.
Otro enfoque de los problemas NP-completos es a través de 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 entrada, pero se puede reformular el problema con un parámetro k para que el problema sea polinomial en términos del tamaño de entrada pero exponencial en términos del parámetro k. En algunas situaciones, esto permite encontrar algoritmos que son “tratables” para valores pequeños de k.
http://en.wikipedia.org/wiki/Parameterized_complexity
http://fpt.wikidot.com/
Comentarios y calificaciones de la guía
Si te ha sido de provecho este post, te agradeceríamos que lo compartas con el resto entusiastas de la programación así contrubuyes a dar difusión a esta información.