Material académico dígital en pdf gratuito para estudiantes y profesores

REDUCCIÓN EN COMPUTABILIDAD PDF TEORÍA Y EJEMPLOS RESUELTOS DE MATEMÁTICAS

Para ilustrar la noción de reducción de una manera informal recurrimos al ejemplo de B. Moret [Mor 98]. Un matemático está en una habitación que contiene una mesa, un grifo y un recipiente vacío en el suelo. Se le pide que ponga el recipiente lleno de agua en la mesa. Rápidamente coge el recipiente, lo llena de agua y lo coloca en la mesa. Un rato más tarde está en la habitación equipada como antes, con la diferencia de que ahora el recipiente está lleno en el suelo. Cuando se le pide que resuelva la misma tarea, el matemático vacía el recipiente, lo deja en el suelo y responde: "he reducido la tarea al primer problema".
Idea intuitiva de reducción
El esquema de la reducción

Related Posts Plugin for WordPress, Blogger...