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.

Problema Simple Insoluble


Se dice 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 instancia del problema P1 en una instancia del problema P2 en tiempo polinomial determinístico.

Ejemplo

Ordenar se reduce a encontrar el menor

Sabemos que existe Menor(i; j), que devuelve el elemento menor del segmento del arreglo A[i, j].

Ejemplo

PROCEDIMIENTO Ordena(A; n)

COMIENZA

PARA i =1 A n HAZ

j = Menor(i; n)

intercambia(i; j)

FINPARA

TERMINA

Funciones Computables


Las funciones computables son una formalización de la noción intuitiva de algoritmo y según la Tesis de Church-Turing son exactamente las funciones que pueden ser calculadas con una máquina de cálculo. La noción de la computabilidad de una función puede ser relativizada a un conjunto arbitrario de números naturales A, o equivalentamente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas por un oracle por A o f. Tales funciones puede ser llamados A-computable o f-computable respectivamente. Antes la definición preciso de una función computable los matemáticos usaban el término informa efectivamente computable.

Las funciones computables son usadas para discutir computabilidad sin referirse a ningún modelo de computación concreto, como máquina de Turing o máquina de registros. Los axiomas de Blum pueden ser usados para definir una teoría de complejidad computacional abstracta sobre el conjunto de funciones computables.



Problemas Insolubles Para La teoria de Lenguajes

Sea el problema Y el siguiente:

P: ¿Existe un procedimiento efectivo capaz de determinar si una máquina de Turing se

detiene sobre alguna cadena?

Para demostrar que Y 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 Y

implica la solubilidad de P. Expresado de otra manera, demostramos que P se reduce a

Y.

Demostración:

Supongamos que Y es un problema de decisión soluble. Al ser un problema soluble,

entonces existe un procedimiento efectivo (o máquina universal de Turing), X, que

resuelve Y. X 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

X 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.

Construyamos a partir de X, un procedimiento efectivo (o máquina universal de Turing)


Detención

La máquina Detención recibe como entrada un par (T’,α), el problema Y solo tiene

como entrada una máquina de Turing, por lo que necesitamos un proceso adicional que

combine T’ y α de manera que las respuestas de X, respondan el problema de la

detención. Este proceso adicional se lleva a cabo en la máquina universal ΔX que realiza lo

siguiente:

a. Recibe como dato de entrada la máquina de Turing T’ y la cadena α.

b. Construye una máquina de Turing T tal que:

Para la cadena α se comporta como la máquina de Turing T’.

Para toda cadena que no sea α la nueva máquina T nunca se detiene o cicla

indefinidamente.

Combinando la máquinas universales X y ΔX, tenemos la máquina universal Detención

que tiene el siguiente comportamiento:

1. Detención recibe como entrada el par (T’, α).

2. La máquina universal Detención utiliza ΔX, la cual a partir de T’ y α construye la

nueva máquina de Turing T.

3. La máquina de Turing T obtenida en el paso anterior es ingresada a la máquina

universal X.

4. Si la respuesta de X es 1 entonces T se detiene para alguna cadena. De la

manera en la que construimos T esa cadena necesariamente es la cadena α (ya que

para el resto sabemos que la máquina siempre cicla) como el comportamiento de T

frente a la cadena α es el mismo que tiene la máquina T’ entonces podemos

afirmar que T’ se detiene sobre α y que por lo tanto Detención emite un 1

5. Si la respuesta de X es 0 entonces T no se detiene para ninguna cadena. De la

manera en la que construimos T la única cadena sobre la que T podía detenerse era

α y que el comportamiento frente a esta cadena era el mismo que el de la máquina

T’. Podemos entonces afirmar, que la máquina de Turing T’ tampoco se detiene

frente a la cadena y que por lo tanto la respuesta que emite Detención es igual a 0.

Conclusión:

• La máquina universal Detención retorna 1 (T’ se detiene sobre α) si X

retorna 1 (T se detiene sobre alguna cadena).

• La máquina universal Detención retorna 0 (T’ no se detiene sobre α) si X

retorna 0 (T se detiene sobre ninguna cadena).

Hemos mostrado como construir la máquina universal Detención que resuelve el

problema de la detención a partir de la máquina universal X que resuelve un

problema que supusimos soluble.

Sabemos por hipótesis que el problema de la detención es un problema insoluble, por

lo tanto la solución encontrada mediante la máquina universal Detención no puede

existir. Lo que implica que alguno de sus componentes no puede existir, es decir

X, o bien ΔX no existe. Como por construcción ΔX existe, luego X no

puede existir.

Podemos entonces concluir que Y es un problema no-soluble.

 

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