Saltar al contenido principal

Reducciones

Las reducciones se usan en el diseño de algoritmos para encontrar una solución a un problema desconocido mediante reducirlo a uno conocido (por ejemplo, reducir el problema de encontrar elementos repetidos en un arreglo al de ordenarlos y hacer una pasada buscando repetidos consecutivos). En cambio, en la teoría de NP-completitud, se demuestra que un problema es NP-completo mediante reducir un problema NP-completo conocido a él. Es decir, operamos en la dirección contraria: el problema conocido se reduce al problema desconocido.

En el caso de cotas inferiores, la idea es similar a la de NP-completitud. Supongamos que tenemos un problema PP para el que queremos establecer una cota inferior, y conocemos un problema QQ con una determinada cota inferior Ω(C(n))\Omega(C(n)). Si podemos transformar un input de QQ en uno de PP en tiempo o(C(n))o(C(n)), resolver PP en el input transformado, y luego transformar el output de PP en el de QQ también en tiempo o(C(n))o(C(n)), entonces Ω(C(n))\Omega(C(n)) es también una cota inferior para el problema PP. De no ser así, las transformaciones nos darían una solución a QQ de tiempo o(C(n))o(C(n)), lo que es imposible.

Esta técnica es general y puede usarse para peor caso y caso promedio, si bien generalmente se usa para establecer órdenes de magnitud y no cantidades exactas de operaciones.