Teoria de la computacion

¿Qué es la Reducibilidad? Una reducción es una forma de convertir un problema en otro problema de tal forma que la solución que se le da al segundo problema pueda ser usada para resolver el primero.La reducibilidad siempre envuelve dos problemas, a los cuales les podemos llamar A y B, si A se reduce a B, podemos usar la solución de B para solucionar A. Así en nuestro ejemplo A es el problemapara encontrar un camino para cruzar la ciudad, y B es el problema de obtener el mapa. Note que la reducibilidad no dice nada acerca de resolver A y B de forma separada, pero si habla acerca de lasolución de A con respecto a obtener la solución de B.
Lo siguiente está más alejado de los ejemplos de reducibilidad.
En la reducibilidad también se producen problemas matemáticos. Por ejemplo elproblema de medición el área de un rectángulo se reduce al problema de medir alto por ancho. El problema es solucionado con un sistema lineal de ecuaciones y esto se reduce al problema de invertir unamatriz.
La reducibilidad juega un importante papel en la clasificación de problemas por decidibilidad y después en la complejidad así como en la teoría.
Cuando A es reducible a B, la solución de A nopuede ser tan difícil que la solución de B, porque la solución de B da la solución de A. En términos de teoría de la computación si A es reducible a B y B es decidible, A también es decidible.Equivalentemente si A es indecidible y reducible a B, B es indecidible.

La reducibilidad siempre envuelve dos problemas, a los cuales les podemos llamar A y B, si A se reduce a B, podemos usar lasolución de B para solucionar A. Así en nuestro ejemplo A es el problema para encontrar un camino para cruzar la ciudad, y B es el problema de obtener el mapa. Note que la reducibilidad no dice nada acercade resolver A y B de forma separada, pero si habla acerca de la solución de A con respecto a obtener la solución de B.
Lo siguiente está más alejado de los ejemplos de reducibilidad....