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:
- 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.
- 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.
- 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!
fuente
Respuestas:
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.
fuente