환산 (복잡도)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

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

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

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

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

정의[편집]

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

\exists f \in F \mbox{ . } \forall x \in \mathbb{N} \mbox{ . } x \in A \Leftrightarrow f(x) \in B

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

A \leq_{F} B

S{\color{Blue}P}(\mathbb N)의 부분집합이고 ≤가 환산 연산자라고 하자. 그러면 다음 조건을 만족할 때 S는 ≤에 대해 닫혀 있다고 한다.

\forall s \in S \mbox{ . } \forall A \in P(\mathbb{N}) \mbox{ . } A \leq s \Leftrightarrow A \in S

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

\forall s \in S \mbox{ . } s \leq A

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

예시[편집]

같이 보기[편집]