FUNCIONES COMPUTABLES:
Son las que se calculan por programas while si P es un programa while y (x1…x2). Es una lista de variables en P, entonces consideremos a las primeras variables como variables de entrada y a las ultimas como variables de salida. Para n,m que pertenece a N en donde F: Nn = Nm.
Es computable si existe un programa while tal que f=fp.
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
• Sabemos que existe Menor(i; j), que devuelve
el elemento menor del segmento del arreglo
A[i, j].
30-nov-05 28
Ejemplo
PROCEDIMIENTO Ordena(A; n)
COMIENZA
PARA i =1 A n HAZ
j = Menor(i; n)
intercambia(i; j)
FINPARA
TERMINA
