환산 (복잡도)
복잡도 이론과 계산 복잡도 이론에서 환산(reduction 리덕션[*])은 어떤 문제를 다른 문제로 변형하는 과정이다. transformation 트랜스포메이션[*]이라고도 한다.
문제 A가 어떤 과정을 통해 문제 B로 환산된다면 B의 해답을 가지고 A의 해답을 알 수 있기 때문에, A를 푸는 작업이 B를 푸는 작업보다 어려울 수 없다. 이를 A ≤ B라 쓰고, 흔히 ≤의 아랫첨자에 어떤 종류의 환산인지 명시해 주곤 한다. 특정한 환산은 복잡도 종류를 정의하는 데 쓰일 수 있다.
예를 들어, 곱셈 문제를 제곱 문제로 환산하는 경우를 살펴 보자. 만약 덧셈, 뺄셈, 제곱 연산, 2로 나누는 연산만 쓸 수 있다면, 두 숫자의 곱을 다음과 같이 구할 수 있다.
거꾸로 같은 두 수를 곱해서 제곱 연산을 할 수 있으므로 반대 환산도 가능하다. 이런 종류의 환산은 튜링 환산이라 한다.
하지만 환산 과정에 제곱 연산을 단 한 번, 그리고 맨 마지막에 사용할 수 있다는 제약을 가하면 환산은 어려워진다. 이러한 제약이 있다면 어떠한 일반적인 환산 과정이 존재하지 않는데, 같은 무리수를 유리수로부터 계산해야 할 수 있기 때문이다. 하지만 반대로 제곱 연산은 곱셈 한 번을 맨 마지막에 사용하기만 해도 되고, 따라서 일반적으로 '곱셈은 제곱 연산보다 더 어렵다'는 결과를 얻어낼 수 있다. 이런 종류의 환산은 다대일 환산이라 한다.
정의 편집
의 두 부분집합 와 가 주어지고, 정의역과 공역이 모두 이며 합성에 대해 닫힌 함수들의 집합 가 주어진다고 하자. 다음 조건을 만족할 때, 는 로 에 대해 환산 가능하다고 한다.
이를 기호로 다음과 같이 표기한다.
가 의 부분집합이고 ≤가 환산 연산자라고 하자. 그러면 다음 조건을 만족할 때 는 ≤에 대해 닫혀 있다고 한다.
다음 조건을 만족할 때 의 부분집합 는 에 대해 난해하다고 한다. 에 해당하는 문제는 적어도 S에 있는 모든 문제만큼은 어렵다.
의 부분집합 가 에 포함되며 에 대해 난해하면 에 대해 완전하다고 한다. 이러한 에 해당하는 문제는 에 속한 문제들 중 가장 어렵다.