![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/0/02/3SAT_reduced_too_VC.svg/langes-640px-3SAT_reduced_too_VC.svg.png&w=640&q=50)
Reducción (complejidad)
transformación de un problema a otro problema / De Wikipedia, la enciclopedia encyclopedia
En teoría de la computación y teoría de la complejidad computacional, una reducción es una transformación de un problema a otro problema. Dependiendo de la transformación usada, la reducción se puede utilizar para definir clases de complejidad en un conjunto de problemas.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/3SAT_reduced_too_VC.svg/320px-3SAT_reduced_too_VC.svg.png)
Intuitivamente, un problema es reducible a un problema
si las soluciones de
existen y dan una solución para
siempre que
tenga solución.
Así, resolver
no puede ser más difícil que resolver
.
Normalmente, esto se expresa de la forma
, y se añade un subíndice en
para indicar el tipo de reducción utilizada.
Por ejemplo, se usa la letra
como subíndice para indicar que la reducción puede realizarse en tiempo polinomial:
.