¿Todos los problemas de NP tienen una formulación ILP de tamaño polivinílico?

14

Dado que la programación lineal entera es NP-completa, hay una reducción de Karp de cualquier problema en NP. Pensé que esto implicaba que siempre hay una formulación de ILP de tamaño polinómico para cualquier problema en NP.

Pero he visto documentos sobre problemas específicos de NP en los que la gente escribe cosas como "esta es la primera formulación de tamaño polivinílico" o "no se conoce una formulación de tamaño polivinílico". Por eso estoy perplejo.

complexity-theory np-complete reductions linear-programming andy
fuente
8
Deberías señalar un ejemplo o dar una cita más completa;)
hugomg
1
Existe una reducción polinómica de cada problema de NP completo a cualquier otro problema de NP completo. Sin embargo, el hecho de que sepamos que existe no significa que sepamos cómo construirlo.
Joe
3
@Joe bueno, sabemos cómo reducir cualquier problema en NP a 3 sat, y también todas las pruebas prácticas de problemas completos de NP provienen de una cadena de reducciones de 3 sat, por lo que siempre puede componer reducciones de cualquier problema NPC dado a cualquier otro.
Andy
10
@ Andy, ¿no acabas de responder a tu pregunta con ese comentario? Usted sabe que cada instancia de problema NP puede escribirse como una instancia 3-SAT polisada, y sabe que una instancia 3-SAT puede escribirse como una instancia ILP polisizada, y el polinomio aplicado al polinomio es otro polinomio ... ¿qué más puede hacer? esperar de una respuesta?
Artem Kaznatcheev
2
Cuando alguien dice que esta es la primera formulación de tamaño polivinílico, lo que quieren decir es que es la primera formulación explícitamente dada . Las reducciones obtenidas a través de SAT (incluso si uno se ocupa de todos los detalles) no se ven bien y son difíciles de trabajar. Por lo general, queremos formulaciones que sean naturales y fáciles de usar.
Kaveh

Respuestas:

5

Esta respuesta es principalmente un resumen de los comentarios sobre la pregunta anterior.

Si un problema es NP-completo, de hecho puede reducirse a ILP, utilizando las reducciones de Karp (- Joe, Andy). Las afirmaciones de "formulaciones de tamaño polinómico" de un problema a otro, probablemente se entiendan como formulaciones más directas, en oposición a reducciones múltiples a través de SAT (- Kaveh).

Ensalada Realz
fuente
1

Si. Cada problema de NP tiene una formulación de ILP de tamaño polinómico.

Aquí es por qué. Cada problema de NP tiene una formulación de tamaño polinómico como una instancia de SAT. Además, todos los operadores booleanos habituales (OR lógico, AND lógico, NOT lógico, etc.) se pueden expresar en ILP, utilizando un número constante de variables y desigualdades por operador booleano. Consulte Operaciones lógicas booleanas expresas en la programación lineal de enteros cero (uno) (ILP) para obtener detalles sobre cómo hacerlo. Por lo tanto, tenemos como máximo una explosión de tamaño constante al pasar de SAT a ILP. Esto implica que hay una formulación de tamaño polinómico de cada problema NP como un problema ILP.

DW
fuente