Suponga que soy un programador y que tengo un problema de NP completo que necesito resolver. ¿Qué métodos están disponibles para tratar los problemas de la APN? ¿Hay una encuesta o algo similar sobre este tema?

Hay una serie de estrategias bien estudiadas; cuál es el mejor en su aplicación depende de las circunstancias.

• Mejore el tiempo de ejecución del caso más desfavorable
  Con la información específica del problema, a menudo puede mejorar el algoritmo ingenuo. Por ejemplo, hayalgoritmospara Vertex Cover con[1]; Esta es una gran mejora sobre el ingenuoy puede hacer que los tamaños de instancia sean relevantes para usted.c < $O(c^n)$$c < 1.3$$\Omega(2^n)$

• Mejore el tiempo de ejecución esperado
  Utilizando la heurística, a menudo puede diseñar algoritmos que son rápidos en muchos casos. Si esos incluyen la mayoría de los que conoces en la práctica, eres dorado. Los ejemplos son SAT para los que existen solucionadores bastante involucrados, y el algoritmo Simplex (que resuelve un problema polinómico, pero aún así). Una técnica básica que a menudo es útil es ramificar y unir .

• Restrinja el problema
  Si puede hacer más suposiciones sobre sus entradas, el problema puede volverse fácil.

  • Propiedades estructurales
    Sus entradas pueden tener propiedades que simplifican la resolución del problema, por ejemplo, planaridad, bipartita o falta un menor para los gráficos. Vea aquí algunos ejemplos de clases de gráficos para las cuales CLIQUE es fácil.
  • Funciones de límite de la entrada
    Otra cosa a tener en cuenta es la complejidad parametrizada ; algunos problemas se pueden resolver en el tiempo para algún parámetro de instancia (grado máximo de nodo, peso máximo de borde, ...) constante. Si puede enlazar por una función polilogarítmica en en su configuración, obtendrá algoritmos polinomiales. Saeed Amiri da detalles en su respuesta .k m k $O(2^kn^m)$$k$$m$$k$$n$
  • Límites de cantidades de entrada
    Además, algunos problemas admiten algoritmos que se ejecutan en tiempo pseudo-polinomial , es decir, su tiempo de ejecución está limitado por una función polinómica en un número que es parte de la entrada; La ingenua comprobación de primalidad es un ejemplo. Esto significa que si las cantidades codificadas en sus instancias tienen un tamaño razonable, es posible que tenga algoritmos simples que se comporten bien para usted.

• Debilitar el resultado
  Esto significa que tolera resultados erróneos o incompletos. Hay dos sabores principales:

  • Algoritmos probabilísticos
    Solo obtienes el resultado correcto con cierta probabilidad. Hay algunas variantes, los algoritmos más notables de Montecarlo y Las Vegas . Un ejemplo famoso es la prueba de primalidad de Miller-Rabin .
  • Algoritmos de aproximación
    Ya no busca soluciones óptimas sino soluciones casi óptimas. Algunos algoritmos admiten límites relativos ("no peor que el doble del óptimo"), otros absolutos ("no peor que más el óptimo") límites en el error. Para muchos problemas está abierto qué tan bien se pueden aproximar. Hay algunos que se pueden aproximar arbitrariamente bien en tiempo polinómico, mientras que se sabe que otros no lo permiten; verifique la teoría de los esquemas de aproximación de tiempo polinómico .$5$

Consulte Algoritmos para problemas difíciles de Hromkovič para un tratamiento completo.

1. La simplicidad es belleza: límites superiores mejorados para la cubierta de vértices por Chen Jianer, Iyad A. Kanj, Ge Xia (2005)

Otras respuestas han abordado esto desde una perspectiva más teórica. Aquí hay un enfoque más práctico.

Para problemas de decisión "típicos" con NP completo ( "¿existe algo que satisfaga todas estas restricciones?" ), Esto es lo que siempre intentaría primero:

1. Escriba un programa simple que codifique su instancia de problema como una instancia de SAT .

2. Luego tome un buen solucionador SAT , ejecútelo (usando la computadora multi-core más rápida que tenga) y vea qué sucede.

Pruebe con instancias más pequeñas primero para tener una idea de cuánto tiempo puede tomar.

Sorprendentemente, este enfoque es mucho mejor que tratar de implementar su propio solucionador específicamente para su problema actual:

• Los solucionadores SAT son muy inteligentes y están bien optimizados. Superan fácilmente su propia implementación de búsqueda de retroceso (no importa cuánto tiempo pierda optimizando su código). También superan fácilmente muchas alternativas fuera de sí, como los solucionadores de programación lineal de enteros.

• Esto requiere muy poca programación. El paso 1 es relativamente sencillo y no es crítico para el rendimiento; puedes usar lenguajes de script como Python. Alguien más ya se ha encargado de implementar todo lo que necesita para el paso 2.

Para los problemas típicos de optimización NP-hard ( "encuentre la cosa más pequeña que satisfaga todas estas restricciones" ) este enfoque puede o no funcionar.

Si puede convertirlo fácilmente en un problema de decisión ( "¿existe una cosa de tamaño 4 que satisfaga todas estas restricciones?" , "¿Qué pasa con el tamaño 3?" ), Genial, siga el mismo enfoque que el anterior con los problemas de decisión.

De lo contrario, es posible que desee recurrir a un solucionador heurístico que intente encontrar una solución pequeña (no necesariamente la solución más pequeña ). Por ejemplo:

1. Codifique su problema como una instancia MAX-SAT (ponderada) .

2. Utilice los solucionadores heurísticos del paquete UBCSAT . Los solucionadores heurísticos se paralelizan trivialmente; trate de encontrar un grupo de computadoras con cientos de computadoras. Puede ejecutar los solucionadores todo el tiempo que desee y luego tomar la mejor solución que haya encontrado hasta ahora.

Complejidad Parametrizada

Una forma de atacar la intractabilidad es pensar en el problema en el contexto de complejidad parametrizada.

En la complejidad parametrizada , resolvemos el problema arreglando algún parámetro (digamos ). Si podemos resolver algún problema en el tiempo , decimos que el problema es un parámetro fijo manejable en . Aquí es solo una función computable. Hay muchos problemas NP-hard que son FPT, sin embargo, hay muchos problemas en NP que se cree que no son parámetros fijos manejables.f ( k ) ⋅ p ( n ) k f ( k $k$$f(k) \cdot p(n)$$k$$f(k)$

Si arreglando algún parámetro podemos resolver un problema en el tiempo , se dice que este problema está en XP. Creemos que XP no es igual a FPT (tal como creemos P NP). Pero también hay muchos problemas entre estos dos (FPT y XP), y hemos definido una jerarquía (en realidad varias), una de las cuales es la jerarquía W. En la jerarquía W, tiene reducciones como la reducción en las clases NP-completas, excepto que no estamos buscando reducciones polytime, solo necesitamos una reducción FPT. La clase W [0] es la clase FPT.$O(n^{f(k)})$$\neq$

Estas son algunas muestras en diferentes clases de la jerarquía W:

1. La cubierta del vértice es FPT (también lo son los caminos separados del vértice en gráficos no dirigidos)
2. Conjunto independiente y Clique son ambos W [1] -completo
3. El conjunto dominante es W [2] -Completo.

Estos son otro nivel de complejidades para clasificar los problemas de NP de manera más precisa y, si desea más, puede consultar la Complejidad de circuitos parametrizados y la Jerarquía W de Downey et al (1998).

Y si quieres aún más, es bueno leer la teoría de la complejidad parametrizada de Flum y Grohe .

Y finalmente:

Complejidad parametrizada versus algoritmos de aproximación:

Se sabe que si el problema tiene FPTAS ( esquema de aproximación de tiempo completamente polinomial ), entonces también es FPT (lo cual es obvio). Pero no hay nada bien conocido en dirección inversa, también hay algunos trabajos sobre la relación de PTAS y XP, pero hay No es una relación muy estrecha entre PTAS y la jerarquía W (al menos no lo sé en este momento).

También en algunos casos, es posible que arreglemos algunos parámetros diferentes, por ejemplo: la longitud de una ruta más larga en el gráfico está limitada y el tamaño de una solución está limitado (por ejemplo, en el conjunto de vértices de retroalimentación), ...

Ejemplos de usos prácticos:

Puede ser que algunas personas crean que la complejidad parametrizada es inútil en la práctica. Pero esto está mal. Muchos de los algoritmos parametrizados se descubren en aplicaciones del mundo real, cuando puede corregir algunos parámetros, aquí hay un ejemplo:

1. Uno de los principales teoremas de la complejidad parametrizada es el de Courcell, que proporciona un algoritmo de tiempo de ejecución para algunas clases de problemas parametrizados. El número de torres de es , lo que significa que para , es imposible. Pero, un grupo implementó su algoritmo con algunas modificaciones en casos más especiales, y obtuvieron un algoritmo extremadamente rápido para la cobertura de vértices, que actualmente se usa en algunas estaciones de metro en Alemania.2 O ( k ) k = $2^{.^{.^{.^2}}}O(n)$$2$$O(k)$$k=10$

2. Uno de los algoritmos heurísticos más rápidos y precisos para TSP es: la fusión de recorridos y la descomposición de ramificación , que utiliza la parametrización del problema (no directamente, pero la descomposición de ramificación y el enfoque de programación dinámica que utilizaron se basa en algunas buenas suposiciones).

La integridad de NP se trata de la intractabilidad del peor de los casos. Según el problema en el que esté trabajando, muchas clases de instancias pueden resolverse en un tiempo razonable en la práctica (aunque es posible que necesite un algoritmo más especializado para obtener los buenos tiempos de ejecución).

Considere ver si hay una reducción eficiente de su problema a un problema con buenos solucionadores disponibles, como la Satisfacción booleana o la Programación lineal entera.

Tiene tres opciones en general: la primera es considerar casos especiales de su problema . En algunos casos especiales, su problema puede resolverse polinomialmente, por ejemplo, determinar si existe una ruta simple de a a en un gráfico dirigido arbitrario es NP-Completo, pero será polinomial (lineal) cuando sea ​​reducible. La segunda opción es usar un buen algoritmo de estimación para resolver su problema. Los algoritmos de estimación brindan respuestas casi óptimas a su problema. Si no puede usar las opciones anteriores, la única forma restante será: usar un algoritmo tolerable para resolver su problema en tiempo exponencialv j v k G $v_i$$v_j$$v_k$$G$$G$. Entre los algoritmos exponenciales, el tiempo de ejecución de algunos de ellos puede ser tolerable cuando el tamaño de entrada de su problema es menor que un valor específico.

Aunque se mencionó brevemente en algunas de las respuestas, permítanme enfatizar que en la práctica, los problemas de NP completo se resuelven (o se aproximan) todo el tiempo. La razón principal por la que puede resolver problemas NP-completos en la práctica es:

Las instancias encontradas en la práctica no son el "peor de los casos".

Otra razón de la discrepancia es:

Es difícil analizar algoritmos heurísticos formalmente.

En la práctica, utiliza algoritmos heurísticos para resolver sus problemas de NP completo y espera lo mejor. Los resultados son a menudo impresionantes.

Otro tema mencionado en otras respuestas es:

A veces, los algoritmos exponenciales son lo suficientemente rápidos.

Eso, por supuesto, depende del problema. Cuando se trata de big data, tenemos la máxima opuesta:

A veces, los únicos algoritmos factibles son cuasilineales.

Me temo que la multitud aquí es bastante teóricamente inclinada. Puede obtener mejores respuestas en el sitio principal de stackexchange.