Reducir un problema X a un problema np-completo Y.

Question

Digamos que tengo un problema X que puedo reducir a un problema NP-completo Y. ¿Puedo asumir que el problema X está en NP? ¿Puede no estar en NP?

Answer 1

Por reducción del problema $X$ al problema $Y$ queremos decir que existe un algoritmo de tiempo polinómico $A$ que toma una instancia $x$ de $X$ y produce una instancia $A(x)$ de $Y$ de tal manera que la respuesta a $A(x)$ es "sí" si y sólo si la respuesta a $x$ es "sí". El tamaño de $A(x)$ es como máximo polinomial en el tamaño de $x$ . Si $Y$ es NP-completo, debe ser en particular en NP, por lo que hay un
verificador no determinista de tiempo polinomial para $Y$ . Aplicando esto a $A(x)$ da un verificador no determinista de tiempo polinómico para $X$ . Así que sí, $X$ debe estar en NP.