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