Reducibilidad

Instituto Tecnológico de Jiquilpan

Teoría de la Computación

Unidad VI.- Reducibilidad

Jiquilpan, Michoacán a 01/Dic/10

Introducción

En el presente trabajo se expone un tema llamado redubilidad, veremos lo que es y se entenderá mejor con ejemplos, así como también veremos algunos temas desglosados de la reducibilidad obviamente con sus respectivas definiciones y aplicaciones.Se pretende entender bien el tema de reducibilidad ya que es un tema básico que nos servirá para poder resolver o no problemas que se nos puedan atravesar en nuestra vida cotidiana diaria.

Redubibilidad

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 uncamino 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 nodice 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 solucionadocon 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 lacomputació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.
Problemas Insolubles Teoría de Lenguajes
Sea el problema Palguna el siguiente problema: Pacept: ¿Existe un procedimiento efectivo capaz de determinar si una máquina de Turing se detiene sobre alguna cadena?
Para demostrar que Palguna no es soluble,comenzaremos suponiendo que lo es, llegando de esta manera a un absurdo. Este absurdo tendrá lugar debido a que la solubilidad de Palguna implica la solubilidad de Pdet. Expresado de otra manera, demostramos que Pdet se reduce a Palguna.
Demostración:
Supongamos que Palguna es un problema de decisión soluble. Al ser un problema soluble, entonces existe un procedimiento efectivo (o máquinauniversal de Turing), Alguna, que resuelve Palguna. Alguna toma como datos de entrada la descripción de una máquina de Turing T y determina en un tiempo finito si T se detiene sobre alguna cadena o no. Es decir Alguna recibe como entrada (T) y retorna un 1 si T se detiene para alguna cadena, mientras que devuelve la salida 0 si T no se detiene para ninguna cadena.

Un problema simple insoluble
Sedice que un problema L1 se reduce en tiempo polinomial determinístico a otro problema L2, si asumiendo que existe un algoritmo A2 en P que resuelve L2 es posible construir un algoritmo A1 en P que resuelva L1.
Escribiremos L1 W L2 para significar que L1 se reduce a L2. Intuitiva: Una problema P1 se reduce polinomialmente a otro problema P2, si existe un algoritmo que transforme una instanciadel problema P1 en una instancia del problema P2 en tiempo polinomial determinístico.

Funciones Computables

En teoría de la computabilidad funciones computables o funciones Turing-computables son los objetos básicos de estudio. Hacen nuestras nociones intuitivas de algoritmo presicas y según el tesis Church-Turing son exactamente las funciones que pueden ser calculados con una máquina de...