¿Qué es la reducción en la teoría de la complejidad computacional?

Como Justin dijo correctamente, las reducciones se trata de usar el hecho de que conoces un algoritmo para que un problema resuelva otro. Digamos que quiere resolver A, pero no está seguro de cómo hacerlo. Si puede reducir A a B, puede usar el algoritmo de B para resolver instancias de A. En cierto sentido, ha demostrado que la facilidad de B puede usarse para mostrar que A es tan fácil. Obviamente, A no puede ser más difícil que B, porque como sabes que hay un algoritmo eficiente B (es decir, B es fácil) y puedes usar ese algoritmo para que B resuelva A, entonces si A era realmente más difícil que A, entonces tal el algoritmo para B no debería existir, o al menos la reducción no debería existir. En cierto sentido, usted mostró que A es tan fácil como B:

[matemáticas] A \ leq_R B [/ matemáticas]

Así es como se usan las reducciones en el campo de los algoritmos. es decir, cómo resolver problemas y elaborar algoritmos para resolver los problemas de interés.

Pero la teoría de la complejidad computacional se trata más de mostrar dureza. es decir, que es muy probable que no exista un algoritmo eficiente para su problema. ¿Cómo haces eso? Bueno, en este caso, suponga que tiene un problema, diga A, que se sabe que es difícil. Pero estamos interesados ​​en resolver B. Si reducimos A a B, hemos demostrado que si existe un algoritmo eficiente para B, entonces existe un algoritmo eficiente para A. es decir

[matemáticas] A \ rightarrow_R B [/ matemáticas]

Pero si A es difícil, entonces se supone que no existe un algoritmo para A. Por lo tanto, no puede existir ningún algoritmo para B (si existiera un algoritmo eficiente para B, entonces contradiría el hecho de que A es difícil). Por lo tanto, mostramos que B es difícil. En cierto sentido, dijimos, B es tan difícil como A:

[matemáticas] A \ leq_R B [/ matemáticas]

Si no fuera tan difícil como A, estaríamos transformando un problema, que se sabe que es difícil, en un problema más fácil, que no tiene sentido (si por alguna razón, la reducción fue válida y, de hecho, B tenía un algoritmo eficiente, entonces demostró que P = NP, es decir, demostró que cada problema que es difícil en realidad … ¡es fácil! Lo que se cree que es bastante improbable). Por lo tanto, B tiene que ser difícil.

Obviamente, el algoritmo de reducción también tiene que ser eficiente para que esto se aplique.