환산 (복잡도)

복잡도 이론과 계산 복잡도 이론에서 환산(reduction 리덕션^[*])은 어떤 문제를 다른 문제로 변형하는 과정이다. transformation 트랜스포메이션^[*]이라고도 한다.

문제 A가 어떤 과정을 통해 문제 B로 환산된다면 B의 해답을 가지고 A의 해답을 알 수 있기 때문에, A를 푸는 작업이 B를 푸는 작업보다 어려울 수 없다. 이를 A ≤ B라 쓰고, 흔히 ≤의 아랫첨자에 어떤 종류의 환산인지 명시해 주곤 한다. 특정한 환산은 복잡도 종류를 정의하는 데 쓰일 수 있다.

예를 들어, 곱셈 문제를 제곱 문제로 환산하는 경우를 살펴 보자. 만약 덧셈, 뺄셈, 제곱 연산, 2로 나누는 연산만 쓸 수 있다면, 두 숫자의 곱을 다음과 같이 구할 수 있다.

a\times b={\frac {(a+b)^{2}-a^{2}-b^{2}}{2}}

거꾸로 같은 두 수를 곱해서 제곱 연산을 할 수 있으므로 반대 환산도 가능하다. 이런 종류의 환산은 튜링 환산이라 한다.

하지만 환산 과정에 제곱 연산을 단 한 번, 그리고 맨 마지막에 사용할 수 있다는 제약을 가하면 환산은 어려워진다. 이러한 제약이 있다면 어떠한 일반적인 환산 과정이 존재하지 않는데, ${\sqrt {2}}$ 같은 무리수를 유리수로부터 계산해야 할 수 있기 때문이다. 하지만 반대로 제곱 연산은 곱셈 한 번을 맨 마지막에 사용하기만 해도 되고, 따라서 일반적으로 '곱셈은 제곱 연산보다 더 어렵다'는 결과를 얻어낼 수 있다. 이런 종류의 환산은 다대일 환산이라 한다.

정의

$\mathbb {N}$ 의 두 부분집합 $A$ 와 $B$ 가 주어지고, 정의역과 공역이 모두 $\mathbb {N}$ 이며 합성에 대해 닫힌 함수들의 집합 $F$ 가 주어진다고 하자. 다음 조건을 만족할 때, $A$ 는 $B$ 로 $F$ 에 대해 환산 가능하다고 한다.