[shaka_shadow]

Hola, buenas noches soy nuevo acá y en el estudio de los algoritmos, pero deseo aprender, así que estuve intentando con este problema, pero después de unas horas desistí, porque no sé cómo expresar un argumento lógico para darle solución al siguiente problema.

Defínase un problema P-completo como un problema X que está en P y que cualquier
otro problema de P puede reducirse en tiempo polinomial a X. Suponga que P distinto de NP.
Demuestre que si X es P-completo entonces X no es NP-completo.

Buenas noches cualquier ayuda sería muy bien recibida.

[Luis Fuentes]

Hola

Hola, buenas noches soy nuevo acá y en el estudio de los algoritmos, pero deseo aprender, así que estuve intentando con este problema, pero después de unas horas desistí, porque no sé cómo expresar un argumento lógico para darle solución al siguiente problema.

Defínase un problema P-completo como un problema X que está en P y que cualquier
otro problema de P puede reducirse en tiempo polinomial a X. Suponga que P distinto de NP.
Demuestre que si X es P-completo entonces X no es NP-completo.

Buenas noches cualquier ayuda sería muy bien recibida.

Si \( P \) distinto de \( NP \) existe un problema \( Y \) que es \( NP \) pero no \( P \).

Si \( X \) es \( NP \)-completo, entonces el problema \( Y \) se puede reducir a \( X \) en tiempo polinomial; pero entonces si además \( X \) es completo, \( Y \) se podría resolver en tiempo polinomial y sería de tipo \( P \).

Saludos.