[martiniano]

Hola.

Estoy ayudando a un amigo a sacarse una asignatura en la que analizan la tratabilidad de algoritmos y en la que se estudian algunos problemas NP-completos como los que defino a continuación.

El problema \( BINPACK(v_1,...v_n;k;V)  \) consiste en decidir si dado un conjunto de \( n \) objetos de tamaños \( v_1,...,v_n \) estos se pueden empaquetar en \( k \) cajas iguales de tamaño \( V \) sin exceder el tamaño de las cajas y sin romper ningún objeto.

El problema \( SUMSET(a_1,...,a_n;c)  \) consiste en decidir si dado un conjunto de \( n \) enteros \( A=\{a_1,...,a_n\} \) y un entero \( c \) existe un subconjunto \( S\subseteq{A} \) tal que su suma sea igual a \( c \).

Resulta que el otro día en un examen se pidió que se redujera polinómicamente el problema BINPACK al problema SUMSET. Cuando me lo comentó empecé a darle vueltas al asunto sin encontrar una reducción explícita. Está claro que la reducción existe porque ambos son problemas NP-complentos, pero no soy capaz de hallarla. Sí que tengo una reducción del problema SUMSET al problema BINPACK, pero claro, al revés me parece mucho más complicado.

Spoiler

Si se quiere resolver el problema \( SUMSET(a_1,...,a_n;c) \) se puede calcular \( N=\displaystyle\sum_{i=1}^n{a_i} \) y luego resolver el problema  \( BINPACK(a_1,...a_n,2c-N;2;c)  \). Es sencillo probar que que ambas sentencias son equivalentes y que no se pierde generalidad al considerar \( 2c-N\geq{0} \) (añadido).

[cerrar]

El caso es que ayer los profesores facilitaron su solución al examen y la que dieron a este ejercicio es incorrecta. Yo pienso que es posible que se les haya colado la pregunta y que no corresponda para nada con lo que se estudia en el curso, con lo que mi amigo estaría en condiciones de reclamar que se anulase la pregunta y con ello llegar al aprobado. No obstante, me apetecía exponer aquí lo ocurrido a ver si alguien sabe de una reducción como la que se pidió en el examen o un bosquejo de cómo podría ser.

Muchas gracias de antemano por vuestros comentarios. Un saludo.

[geómetracat]

Como parece que nadie contesta: yo lo he estado pensando un rato antes y no me ha salido. A primera vista no parece fácil. En cualquier caso, si los profesores han puesto una solución incorrecta se podrá reclamar. Por curiosidad, ¿puedes poner la solución incorrecta? (por ver si se puede arreglar de alguna manera, o para ver si se puede saber en qué estaban pensando cuando pusieron el problema).

[martiniano]

Hola.

Muchas gracias por responder, geómetracat. Adjunto la solución oficial. Es el quinto ejercicio. Como ya me ha pasado otras veces, el documento que adjunto está en catalán, que es lo que hablamos por aquí. Yo diría que se entiende bastante bien para alguien que hable castellano. No obstante, si alguien tiene alguna duda idiomática yo estaría encantado de aclarársela.

La solución además de incorrecta es sospechosa. Empieza definiendo el problema BIN_PACK de forma diferente a como lo hacen en los apuntes y en las clases, que sería la definición que he dado en el primer mensaje del hilo. A pesar de ello, y aún asumiendo la nueva definición, la solución es claramente errónea, ya que lo que viene a decir es que una palabra de la forma \( (v_1,...,v_n,V,k) \) pertenece a BIN_PACK si y sólo si la palabra \( (v_1,...,v_n,V\cdot{}k) \) pertenece a SUM_SET. Esto es claramente falso, por ejemplo \( (3,3,2;8) \) pertenece a SUM_SET porque en \( A=\{3,3,2\} \) hay un subconjunto que suma \( 8 \), el propio \( A \). Sin embargo, \( (3,3,2;4;2) \) no pertenece a BIN_PACK, ya que no hay manera de empaquetar objetos de volúmenes 3, 3 y 2 en dos cajas de volumen 4. Observa que da igual cuál de las dos definiciones de BIN_PACK tengas en mente.

A mí, personalmente, me suena todo un poco a que querían pedir otra cosa, probablemente transformar SUM_SET en BIN_PACK y que cuando se dieron cuenta de que lo habían preguntado al revés reaccionaron publicando esto... No sé...

Hoy he estado mirando por encima una demostración del teorema de Cook, que según me ha parecido es constructiva. Es decir, parece que hay un algoritmo que permite transformar cualquier problema NP en un problema de satisfacibilidad booleana. Y después, se supone que también existen funciones polinomiales que transforman el problema de la satisfacibilidad booleana en cualquier otro de los NP-completos. No obstante, esto se sale del temario de la asignatura. No han visto ni teorema de Cook, ni el problema de la satisfacibilidad booleana ni nada de eso. Solamente la definición de NP-completo, algunos ejemplos de estos problemas (4 ó 5) y lo que significa transformar polinomialmente un problema en otro. Así que...

Pero bueno, ya que estamos aquí, me gustaría preguntar si alguien conoce algún documento o algo donde se hable de los problemas NP-completos y que incluya las reducciones de unos problemas en otros. Algo así como lo que se vislumbra en la lista de Karp.

De verdad que muchísimas gracias. Un saludo.

[geómetracat]

Pues pensaba que la solución daría más pistas de qué estaban pensando, pero no. Es claramente errónea y no hay manera de arreglarlo.
La verdad es que me he quedado igual, pero sí parece claro que tu amigo debería reclamar.

Sobre el teorema de Cook: si no me equivoco es el que dice que 3SAT es NP-completo. No recuerdo los detalles de la demostración, pero creo que la idea era "simular" una máquina de Turing no determinista con un problema 3SAT.
Sinceramente, no veo cómo vas a sacar de ahí una reducción explícita de un problema NP-completo a otro, ya que aunque tengas reducciones explícitas de BINPACK a 3SAT y de SUMSET a 3SAT no está claro a priori cómo "ir hacia atrás" (una reducción de 3SAT a SUMSET, por ejemplo). En cualquier caso parece bastante complicado, y mucho más para hacerlo en un examen.

Sobre referencias, conozco algunos libros que hablan de NP-completitud, demuestran el teorema de Cook y hacen algunas reducciones, pero no conozco ninguno que sea muy completo, en plan listado de problemas NP-completos con todas sus reducciones.

[martiniano]

Hola.

Sobre el teorema de Cook: si no me equivoco es el que dice que 3SAT es NP-completo. No recuerdo los detalles de la demostración, pero creo que la idea era "simular" una máquina de Turing no determinista con un problema 3SAT.
Sinceramente, no veo cómo vas a sacar de ahí una reducción explícita de un problema NP-completo a otro, ya que aunque tengas reducciones explícitas de BINPACK a 3SAT y de SUMSET a 3SAT no está claro a priori cómo "ir hacia atrás" (una reducción de 3SAT a SUMSET, por ejemplo).

Según tengo entendido la demostración de Cook asegura la existencia de un problema NP, el problema de la satisfacibilidad booleana (SAT), al que se pueden reducir todos los demás problemas NP. Posteriormente, se redujo el problema SAT a otros problemas, como el de la satisfacibilidad de expresiones booleanas de tres variables (3SAT), al problema de la mochila, el del empaquetamiento y a muchos otros...

Lo que me ha parecido sacar de la demostración de Cook es lo siguiente. Primero demuestra que SAT es NP. Después, en la segunda parte, que es a la que yo me refería, prueba que dada una máquina de Turing no determinista que opera en tiempo polinómico y una entrada del problema que resuelve, se puede hallar (y la demostración consiste en hallarla) una expresión booleana que es satisfacible si y sólo si la máquina acepta la entrada. Entonces, si se tiene una máquina de Turing no determinista para un problema NP cualquiera, como el del empaquetamiento, dicho problema se puede reducir polinomialmente al problema SAT y de ahí al problema 3SAT o a cualquier otro de los problemas NP-completos. Creo que las reducciones explícitas que se tienen (yo de momento no todas) son al revés de como dices. Es decir, del problema SAT a otros problemas NP-completos. Son estas reducciones las que creo entender que demuestran que cada uno de los problemas NP-completos conocidos efectivamente lo son.

En cualquier caso parece bastante complicado, y mucho más para hacerlo en un examen.

Claro, más que nada era para mostrar algún avance. Efectivamente, esto no se puede hacer en el tiempo que dieron para responder a esta pregunta. Además, hoy ha pasado algo que apoya la tesis de la errata en el enunciado. Resulta que he hablado con otro conocido que se presentó al examen y a esa pregunta le pusieron un 7/10. Le he preguntado que qué les puso y resulta que les contestó exactamente lo mismo que los profesores proponen en su solución y que no le pusieron el 10 porque sólo prueba la equivalencia en un sentido. Él ve que la equivalencia entre ambas sentencias no es tal, pero claro, contestó así por poner algo y no entregar la pregunta en blanco, ya que no tenía nada. No me extrañaría un pelo que esta persona fuese de las pocas que contestase algo y los profesores le han copiado la respuesta para no desentonar más. En fin... Se ve de todo en este oficio...

Sobre referencias, conozco algunos libros que hablan de NP-completitud, demuestran el teorema de Cook y hacen algunas reducciones, pero no conozco ninguno que sea muy completo, en plan listado de problemas NP-completos con todas sus reducciones.

Gracias igualmente. Yo manejo uno de John E. Hopcroft que se llama Teoría de autómatas, lenguajes y computación. Es ahí donde vi la demostración del teorema de Cook y algunas reducciones del problema SAT a otros problemas NP-completos. Ahora he visto que en Wikipedia también se muestran algunas cosas.

Una vez más, gracias. Un saludo.

[geómetracat]

Según tengo entendido la demostración de Cook asegura la existencia de un problema NP, el problema de la satisfacibilidad booleana (SAT), al que se pueden reducir todos los demás problemas NP. Posteriormente, se redujo el problema SAT a otros problemas, como el de la satisfacibilidad de expresiones booleanas de tres variables (3SAT), al problema de la mochila, el del empaquetamiento y a muchos otros...

Lo que me ha parecido sacar de la demostración de Cook es lo siguiente. Primero demuestra que SAT es NP. Después, en la segunda parte, que es a la que yo me refería, prueba que dada una máquina de Turing no determinista que opera en tiempo polinómico y una entrada del problema que resuelve, se puede hallar (y la demostración consiste en hallarla) una expresión booleana que es satisfacible si y sólo si la máquina acepta la entrada. Entonces, si se tiene una máquina de Turing no determinista para un problema NP cualquiera, como el del empaquetamiento, dicho problema se puede reducir polinomialmente al problema SAT y de ahí al problema 3SAT o a cualquier otro de los problemas NP-completos. Creo que las reducciones explícitas que se tienen (yo de momento no todas) son al revés de como dices. Es decir, del problema SAT a otros problemas NP-completos. Son estas reducciones las que creo entender que demuestran que cada uno de los problemas NP-completos conocidos efectivamente lo son.

Gracias por el recordatorio. Claro, en la demostración del teorema de Cook se prueba que hay una reducción de cualquier problema NP (completo o no) a SAT. Luego para demostrar que un problema A es NP-completo, se da una reducción de un problema B que se sabe que es NP-completo a A (por ejemplo, podría ser B=SAT). Entonces habría que obtener la reducción explícita dada por el teorema de Cook de BINPACK a SAT, y por otro lado encontrar una cadena de reducciones de SAT a SUMSET (que seguro que se conoce porque creo recordar que todas las pruebas de NP-completitud salen en última instancia de que SAT es NP-completo).

Claro, más que nada era para mostrar algún avance. Efectivamente, esto no se puede hacer en el tiempo que dieron para responder a esta pregunta. Además, hoy ha pasado algo que apoya la tesis de la errata en el enunciado. Resulta que he hablado con otro conocido que se presentó al examen y a esa pregunta le pusieron un 7/10. Le he preguntado que qué les puso y resulta que les contestó exactamente lo mismo que los profesores proponen en su solución y que no le pusieron el 10 porque sólo prueba la equivalencia en un sentido. Él ve que la equivalencia entre ambas sentencias no es tal, pero claro, contestó así por poner algo y no entregar la pregunta en blanco, ya que no tenía nada. No me extrañaría un pelo que esta persona fuese de las pocas que contestase algo y los profesores le han copiado la respuesta para no desentonar más. En fin... Se ve de todo en este oficio...

Uf, tiene mala pinta sí. Yo si fuera los profesores diría "hemos metido la pata hasta el fondo" (que oye, a todos nos pasa de vez en cuando) y anularía la pregunta o algo así. Pero veremos a ver, en mi experiencia muchas personas no bajan del burro cuando pasan estas cosas.

Gracias igualmente. Yo manejo uno de John E. Hopcroft que se llama Teoría de autómatas, lenguajes y computación. Es ahí donde vi la demostración del teorema de Cook y algunas reducciones del problema SAT a otros problemas NP-completos. Ahora he visto que en Wikipedia también se muestran algunas cosas.

Yo el único que me he leído entero sobre estas cosas es el de Davis et al. "Computability, complexity and languages". Es un libro que me gustó mucho.

[martiniano]

Hola.

Uf, tiene mala pinta sí. Yo si fuera los profesores diría "hemos metido la pata hasta el fondo" (que oye, a todos nos pasa de vez en cuando)

Por supuesto. Es muy normal equivocarse, independientemente del contexto. No pasa nada. El problema viene si no se reconoce.