Clasificación de la dificultad de los problemas difíciles de NP en la práctica

15

Esta pregunta está estrechamente relacionada con otra publicación: Transiciones de fase en problemas difíciles de NP, pero es algo diferente. Si bien esa pregunta es sobre la dureza de instancias particulares de problemas difíciles de NP, se trata de clasificar la dificultad de las mismas instancias.

Hay mucha bibliografía sobre el efecto conocido como transición de fase . En particular, para el caso de fórmulas aleatorias de 3-SAT en forma conjuntiva normal (CNF), se sabe que existe un valor R de la relación de cláusulas a variables de modo que para todos los r <R la fórmula puede satisfacerse con alta probabilidad y para r> R la fórmula no es satisfactoria con alta probabilidad. El efecto de transición de fase ocurre cerca de R y tiene el notable efecto de que resolver el problema de satisfacción de esas fórmulas es extremadamente difícil en la práctica.

Dado que para probar la dureza NP de un problema dado, es necesario demostrar que hay un tiempo polinomial de reducción de Turing de un problema NP completo y que los problemas NP completos pueden transformarse en tiempo polinómico entre ellos, entonces el La siguiente pregunta surge naturalmente:

¿Es posible clasificar la dificultad de los problemas difíciles de NP en la práctica usando la transición de fase de 3-SAT CNF como indicador? La intuición es que se puede esperar que un problema P1 sea más difícil que P2 si su codificación 3-SAT está más cerca de R (que se sabe que está cerca de 4.2). Tenga en cuenta que esta idea no necesariamente vincula cada instancia particular a una dificultad particular, solo las clasifica.

Hay una serie de argumentos en contra, entre ellos:

  1. La transición de fase de la fórmula 3-SAT CNF se aplica a fórmulas aleatorias. Sin embargo, una instancia particular en un problema diferente tiene alguna estructura que podría ser explotada por los solucionadores de ese problema, esto ya lo señaló Peter Shor en la pregunta antes mencionada.
  2. Es posible que la codificación particular utilizada para transformar las instancias particulares de nuestro problema en 3-SAT juegue un papel crucial en la proporción de cláusulas a variables que conducen a valores engañosos, por lo tanto, Kaveh plantea esta preocupación. Los comentarios a esta pregunta.
  3. Serge (según tengo entendido por su comentario a esta pregunta) plantea el problema de que uno podría complicar artificialmente el problema difícil de NP original de modo que resulte en una fórmula 3CNF que altere la proporción de cláusulas a variables al tiempo que preserva la satisfacción.

En cuanto a 1, todos los problemas pueden compartir la misma clase de regularidad para que se apliquen los problemas de clasificación (en lugar de caracterizar la dificultad); en cuanto a 2, hay codificaciones en problemas particulares que se sabe que no son redundantes con la regla de Propagación de unidades, por lo que deberían preferirse y tal vez eviten esas clasificaciones erróneas. Un ejemplo es Sideris et al., 2010 para el caso de la planificación proposicional. En cuanto a 3, Cheeseman et al., 1991 ya consideraron la cuestión de si los mapeos entre problemas preservan o no el efecto de transición de fase y sus experimentos preliminares parecen apoyar su conjetura, siempre que uno reduzca el problema NP original e incluso eso " puede ser reducido aún más aplicando resolución a las cláusulas ".

¿Todo esto tiene sentido para ti? ¿conoce alguna referencia bibliográfica sobre esto? ¡Cualquier orientación sería ampliamente reconocida!

Carlos Linares López
fuente
Supongo que la respuesta dependería de la reducción particular a SAT que se usa, aunque podría haber una forma de evitarlo.
Kaveh
55
Otro argumento en contra es que siempre se puede agregar un componente disjunto satisfactorio muy escaso o muy denso a una fórmula 3CNF, alterando la relación de cláusulas a variables y preservando su satisfacción.
Serge Gaspers
@Kaveh: muchas gracias por tus comentarios! La idea sería usar codificaciones no redundantes para 3-SAT como en [Sideris et al. 2010]. No estoy afirmando que esto funcione, pero parece ser lo correcto. He editado la pregunta con tu comentario. ¡Gracias de nuevo!
Carlos Linares López
1
@Serge: buen punto Serge! [Cheesemann et al., 1991] ya examinó la cuestión de si los mapeos entre problemas conservan el efecto de transición de fase tanto para los problemas NP como para los problemas en P (para demostrar que no se convierten en NP cuando se extienden artificialmente a 3-SAT, por ejemplo ) y sus resultados respaldan esas afirmaciones siempre que comiencen con algunas reducciones preliminares, tal vez aplicando la regla de Propagación de Unidad. He editado mi pregunta con sus comentarios. ¡Muchas gracias!
Carlos Linares López
@todos: muchas gracias por la atención prestada a mi pregunta! Es mi primera pregunta aquí (y seguramente publicaré otras en el futuro). Me pareció impresionante que en menos de 24 horas recibió 125 visitas, 7 votos y una persona lo marcó como favorito. ¡Gracias a todos!
Carlos Linares López

Respuestas:

13

Si bien no es inconcebible que los obstáculos técnicos que mencionas puedan superarse de alguna manera, creo que actualmente hay muy poca motivación para hacerlo, por la simple razón de que (al menos hasta donde yo sé) la dificultad de NP-hard Los problemas en la práctica parecen, empíricamente, tener poco que ver con su cercanía a la transición de la fase 3-SAT.

Compare esto con otras formas de clasificar los problemas NP-hard en términos de dificultad: existe una correlación empírica entre los problemas NP-hard que son fáciles en la práctica y los problemas NP-hard que son fáciles de aproximar , o que son manejables con parámetros fijos (en el sentido de complejidad parametrizada). Se han desarrollado nociones apropiadas de reducción en estos casos que explican parcialmente las observaciones empíricas. Sin embargo, actualmente no parece haber ninguna indicación empírica de que la mayoría de los problemas difíciles de NP que son difíciles en la práctica son difíciles debido a su estrecha relación con las instancias de 3-SAT cerca de la transición de fase. Por lo tanto, no tiene mucho sentido desarrollar una teoría para "explicar" algo que no parece ser cierto en la práctica.

Timothy Chow
fuente
2
Votado Me interesaría una referencia a la clasificación empírica de los problemas NP-difíciles.
Aaron Sterling
¡Votado también! Pero como Aaron, estaría muy interesado también en algunos baberos de referencia sobre la clasificación de los problemas NP-difíciles. ¡Dame un par y felizmente marcaré esta pregunta como respondida! (Hablando sinceramente, seguramente lo haré en un par de días, incluso si no proporciona referencias de babero) ¡Gracias de nuevo Timothy!
Carlos Linares López
1
W
Timothy !! Muchas gracias de verdad !!! ¡Es muy amable de su parte proporcionar esa referencia de babero! ¡¡Muchas gracias!!
Carlos Linares López