Algoritmia - Problema NP3

Aquí el último problema de la serie!

Yo sigo trabajando por mi parte pero oxidado estoy! Una pena!

Tenemos un problema NP-completo que llamaremos Completo, y otro problema NoLoSabemos que es NP. Queremos demostrar que NoLoSabemos es un problema NP-completo mediante el problema Completo (con una reducción), pero no sabemos mucho sobre la relació entre estos dos problemas. De toda manera, disponemos de una función Oráculo(e, C) que dado un elemento e y un conjunto C, devuelve cierto si y sólo si el elemento e pertence al conjunto C. I tambien disponemos de un conjunto de gunciones que, dado un elemento de NoLoSabemos, devuelve un elemento de Completo. Estas funciones son F1, F2, F3, ..., Fn, es decir, hay n funciones diferentes de NoLoSabemos en Completo. Se sabe que para todo elemente de NoLoSabemos, una de las funciones F calcula una imagen que pertence a Completo, pero no se sabe cual es, y tampoco no es la misma para todo elemento de NoLoSabemos. (por cierto, sabemos que hay un elemento llamado no-completo que no pertenece a Completo).Se debe remarcar que el coste de la función Oráculo y de cada una de las funciones F1, F2, F3,...,Fn es polinímico.

Se pide:
a) ¿Qué hito deberia tener n respecto a NoLoSabemos para poder aprovechar las funciones F y Oráculo para hacer una reducción entre NoLoSabemos y Completo?
b) Asumiendo la restricción del punto (a), hacer una función para demostrar que NoLoSabemos es tambien NP-completo. Se debe demostrar que esta función es una reducción.


Esto es todo que no es poco!!

Gracias a todos!

a) Hito necesario para aprovechar funciones F y oráculo:
Para aprovechar las funciones F y oráculo en una reducción entre NoLoSabemos y Completo, el número de funciones (n) debería ser al menos igual al tamaño de la entrada de NoLoSabemos. Es decir, n debería ser mayor o igual al tamaño del conjunto más grande posible en NoLoSabemos. Esto permitirá que cada elemento de NoLoSabemos tenga una función correspondiente en Completo.

b) Función de reducción de NoLoSabemos a completo:

Dada la restricción del punto (a), asumimos que n es al menos igual al tamaño del conjunto más grande en NoLoSabemos. Ahora, construimos una función de reducción R que transforma instancias de NoLoSabemos en instancias de Completo.

La función de reducción R toma como entrada un elemento x de NoLoSabemos. Utiliza las funciones F1, F2, ..., Fn para obtener imágenes en Completo. Dado que hay al menos una función correspondiente a cada elemento de NoLoSabemos, podemos garantizar que obtendremos al menos n imágenes en Completo.

La función R construye una instancia de Completo con las n imágenes obtenidas y utiliza el Oráculo para verificar si todas las imágenes pertenecen a Completo. Si es así, devuelve esta instancia de Completo; de lo contrario, devuelve una instancia especial que no pertenece a Completo.

Formalmente, la función R se define de la siguiente manera:

R(x)={(y_1 ,y_2,...,y_n) si ∀i, Oráculo(yi,Completo) = cierto
\\ no-completo si ∃i, Oráculo(y_i, Completo) = falso
​
Donde y_i = F_i(x) para 1 ≤ i ≤ n.

Esta función de reducción R se ejecuta en tiempo polinómico, ya que tanto el Oráculo como las funciones F tienen costes polinómicos. Además, R mantiene la propiedad de que si x pertenece a NoLoSabemos, entonces R(x) pertenece a Completo, y si x no pertenece a NoLoSabemos, entonces R(x) no pertenece a Completo.

Con esto, hemos demostrado una reducción polinómica desde NoLoSabemos hasta Completo, lo que implica que NoLoSabemos es NP-completo.