Automatas finitos deterministas

Teoría de la computación.
Periodo: Verano 2012

Docente: Marco Antonio Rodriguez Zuñiga
Tema: Reducibilidad.
Alumno: Edgar O. Alvarado Hdez.

Nª Ctrl. 09041190
FOLIO: 6.1(09041190)Durango, Dgo.Mex

Fecha: 23/07/2012

Introducción.!

3

Reducibilidad.!

3

Reducibilidad de Turing !

3

Conclusiones !

4

2

Introducción.
En el tema anterior estudiamos ladecibilidad ahora nos adentraremos en la investigación
sobre la reducibilidad que ha su vez cobra importancia en la teoría de la computación,
pero antes necesitamos una definición para poder adentrarnos enel tema

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.
• Se dice que un problema L1 se reduce en tiempo polinomial deterministico a otro
problema L2, si asumiendo que existe un algoritmo A2 en P que resuelve L2 es posible
construir un algoritmo A1 enP 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 unainstancia del problema P1 en una instancia del problema P2
en tiempo polinomial deterministico.
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.
Lareducibilidad 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 tandifí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...