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 elprimero.
Por ejemplo suponiendo que quieres encontrar un camino para una nueva ciudad. Tú sabes que esto podría ser fácil si tú tuvieras un mapa. Así tú puedes reducir elproblema encontrando un camino para ir por la cuidad, al el problema de obtener un mapa para ir por la ciudad.
La reducibilidad siempre envuelve dos problemas, a los cualesles 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 problema para encontrar un camino para cruzarla 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 la solución deA 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 el problema 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 ecuacionesy esto se reduce al problema de invertir una matriz.
La reducibilidad juega un importante papel en la clasificación de problemas por decidibilidad y después en lacomplejidad así como en la teoría.

Cuando A es reducible a B, la solución de A no puede ser tan difícil que la solución de B, porque la solución de B da la solución de A. Enté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.