## 3.3.2 REDUCTIBILIDAD

Concepto de reducibilidad

Una reductibilidad es una forma de convertir un problema en otro de tal forma que la solución que se le da al segundo problema pueda ser usada para resolver el primero.

Ejemplo de reducibilidad

Suponiendo que quieres encontrar un camino para una nueva ciudad. Sabes que esto podría ser fácil si tuvieras un mapa. Así, 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. En este caso solo se trata de reducir el problema diviendolo en dos para reducirlo y asi buscar la solución mediante dos problemas. 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.

Reductibilidad polinómica

Supongamos que queremos resolver el problema de decisión A y que tenemos un algoritmo que resuelve el problema de decisión B. Supongamos también que tenemos un algoritmo que construye una instancia y de B para toda instancia x de A de tal forma que un algoritmo para B responde “sí” para y si y solo si la respuesta al problema A para x es “sí”. Dicho algoritmo se denomina algoritmo de transformación. El algoritmo de transformación combinado con el algoritmo para B nos da un algoritmo para A.

Definición

Si existe un algoritmo de transformación polinómico del problema de decisión A en el problema de decisión B, el problema A es reducible polinómicamente al problema B. Lo denotamos:

A ≤p B.

Si el algoritmo de transformación es polinómico y tenemos un algoritmo polinómico para B, intuitivamente parece que el algoritmo para A resultante de la combinación debe ser polinómico.

###