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
0 comentarios:
Publicar un comentario