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.

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 el problema 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 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 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 acerca de 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.

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 ecuaciones y 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 la complejidad 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. 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.
 

© REDUCIBILIDAD
Revolution Elements by Blozard. Original WP theme by Jason Schuller | Distributed by Deluxe Templates