Unidad 6; REDUCIBILIDAD

• 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

TEMAS DE LA UNIDAD

6.1 PROBLEMAS INSOLUBLES TEORIAS DE LENGUAJES

6.2 UN PROBLEMA SIEMPRE INSOLUBLE

6.3 PROBLEMAS COMPUTABLES

6.4 REDUCIBILIDAD DE TURING