환산 (복잡도)

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

복잡도 이론계산 복잡도 이론에서 환산(reduction)은 어떤 문제를 다른 문제로 변형하는 과정이다. transformation이라고도 한다.

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

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

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

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

정의[편집]

의 두 부분집합 가 주어지고, 정의역과 공역이 모두 이며 합성에 대해 닫힌 함수들의 집합 가 주어진다고 하자. 다음 조건을 만족할 때, 에 대해 환산 가능하다고 한다.

이를 기호로 다음과 같이 표기한다.

의 부분집합이고 ≤가 환산 연산자라고 하자. 그러면 다음 조건을 만족할 때 는 ≤에 대해 닫혀 있다고 한다.

다음 조건을 만족할 때 의 부분집합 에 대해 난해하다고 한다. 에 해당하는 문제는 적어도 S에 있는 모든 문제만큼은 어렵다.

의 부분집합 에 포함되며 에 대해 난해하면 에 대해 완전하다고 한다. 이러한 에 해당하는 문제는 에 속한 문제들 중 가장 어렵다.

예시[편집]

같이 보기[편집]