Algoritmia - Problema NP2

Hola!

Aquí el segundo de los problemas que em han pasado.

Un investigador piensa demostrar que P = NP buscando una reducción entre dos problemas, uno de NP-Completo i uno de P. Concretamente, escoge los siguientes problemas: el de MOCHILA (en su versión decisional) i MAXIMO (encontrar el máximo de un vector de enteros, en su versión decsional).

MOCHILA = { Dado un vector N pares (peso i valor) i dos enteros P i V, decidir si existe algun subconjunto de parejas con un valor total >= V i un peso total <= P}
MAXIMO = { Dado un vector de N enteros i un entero M, decidir si existe un número >= M dentro del vector}

Partiendo de estos problemas, plantea la siguiente demostración para P = NP: "Hacemos una reducción polinómica MAXIMO < MOCHILA. la función de reducción f és la siguiente: Dado un vector de N enteros x1...xn i un entero M, generamos una instancia de MOCHILA con N pares : (pes = 1, valor = x1) ... (pes = 1, valor = Xn) i tenemos como P=1 i V = M. Esta función realiza la reducción entre MAXIMO y MOCHILA. Como MOCHILA es un problema NP-Completo i MAXIMO es un problema polinomico (P), la conclusión es que P = NP"

a) Comprueba si la función f satisface las propiedades de una reducción polin´´omica (<p)
a.1) Justifica si tiene coste polinómico
a.2)Justifica si x pertenece a MAXIMO -> f(x) pertence a MOCHILA
a.3) Justifica si x no pertenece a MAXIMO -> f(x) no pertenece a MOCHILA

b) Como se puede suponer, hay un error en la demostración planteada de este ejercicio.
Indicar donde se encuentra el error.

Esto es todo sobre este problema! Es una lástima como por falta de uso se pierde la práctica, me comprometí a ayudar y es que estos problemas que los resolvía cuando estudiaba ahora me veo incapaz de sacarlos!

A ver si alguien me echa una mano! (Y que no sea al cuello)

a) Comprobación de la función f como reducción polinómica (<p):

a.1) Coste polinómico:
La función f genera N pares (peso i valor), lo cual tiene un coste lineal O(N), que es polinómico. Por lo tanto, cumple con esta propiedad.

a.2) Si x pertenece a MAXIMO -> f(x) pertenece a MOCHILA:
Si x pertenece a MAXIMO, significa que hay un número mayor o igual a M en el vector. Al construir la instancia de MOCHILA con pares de peso 1 y valor igual a los elementos del vector, aseguramos que existe un subconjunto con un valor total mayor o igual a M y un peso total igual al número de elementos del vector (N). Por lo tanto, f(x) pertenece a MOCHILA.

a.3) Si x no pertenece a MAXIMO -> f(x) no pertenece a MOCHILA:
Si x no pertenece a MAXIMO, implica que no hay un número mayor o igual a M en el vector. Al construir la instancia de MOCHILA, no habrá un subconjunto con un valor total mayor o igual a M. Por lo tanto, f(x) no pertenece a MOCHILA.

b) Error en la demostración:
La demostración propuesta tiene un error en la conclusión. Aunque se ha demostrado la reducción polinómica de MAXIMO a MOCHILA, no se puede concluir directamente que P = NP. La reducción polinómica solo implica que si podemos resolver MOCHILA eficientemente, también podemos resolver MAXIMO eficientemente. La relación entre P y NP es una cuestión abierta y no se ha demostrado que P sea igual a NP hasta la fecha de mi último conocimiento en enero de 2022.

Sr. Indecible, espero que esta explicación te ayude a comprender y abordar el problema.