환산 (복잡도) 문서 원본 보기

{{위키데이터 속성 추적}}
[[복잡도 이론]]과 [[계산 복잡도 이론]]에서 '''환산'''({{lang|en|reduction|리덕션}})은 어떤 문제를 다른 문제로 변형하는 과정이다. {{lang|en|transformation|트랜스포메이션}}이라고도 한다.

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

예를 들어, [[곱셈]] 문제를 [[제곱]] 문제로 환산하는 경우를 살펴 보자. 만약 덧셈, 뺄셈, 제곱 연산, 2로 나누는 연산만 쓸 수 있다면, 두 숫자의 곱을 다음과 같이 구할 수 있다.
: <math>a \times b = \frac{(a + b)^2 - a^2 - b^2}2</math>
거꾸로 같은 두 수를 곱해서 제곱 연산을 할 수 있으므로 반대 환산도 가능하다. 이런 종류의 환산은 [[튜링 환산]]이라 한다.

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

== 정의 ==
[[자연수|<math>\mathbb N</math>]]의 두 [[부분집합]] <math>A</math>와 <math>B</math>가 주어지고, 정의역과 공역이 모두 <math>\mathbb N</math>이며 [[함수 합성|합성]]에 대해 닫힌 함수들의 집합 <math>F</math>가 주어진다고 하자. 다음 조건을 만족할 때, <math>A</math>는 <math>B</math>로 '''<math>F</math>에 대해 환산 가능'''하다고 한다.
: <math>\exists f \in F \mbox{ . } \forall x \in \mathbb{N} \mbox{ . } x \in A \Leftrightarrow f(x) \in B</math>
이를 기호로 다음과 같이 표기한다.
: <math>A \leq_{F} B</math>
<math>S</math>가 [[멱집합|<math>{\color{Blue}P}(\mathbb N)</math>]]의 부분집합이고 ≤가 환산 연산자라고 하자. 그러면 다음 조건을 만족할 때 <math>S</math>는 ≤에 대해 '''닫혀 있다'''고 한다.
: <math>\forall s \in S \mbox{ . } \forall A \in P(\mathbb{N}) \mbox{ . } A \leq s \Leftrightarrow A \in S</math>
다음 조건을 만족할 때 <math>\mathbb N</math>의 부분집합 <math>A</math>는 <math>S</math>에 대해 '''난해'''하다고 한다. <math>A</math>에 해당하는 문제는 적어도 ''S''에 있는 모든 문제만큼은 어렵다.
: <math>\forall s \in S \mbox{ . } s \leq A</math>
<math>\mathbb N</math>의 부분집합 <math>A</math>가 <math>S</math>에 포함되며 <math>S</math>에 대해 난해하면 <math>S</math>에 대해 '''완전'''하다고 한다. 이러한 <math>A</math>에 해당하는 문제는 <math>S</math>에 속한 문제들 중 가장 어렵다.

== 예시 ==
* 복잡도 종류 [[P (복잡도)|P]], [[NP (복잡도)|NP]], [[PSPACE]]는 [[다항시간 환산]]에 대해 닫혀 있다.
* 복잡도 종류 [[L (복잡도)|L]], [[NL (복잡도)|NL]], [[P (복잡도)|P]], [[NP (복잡도)|NP]], [[PSPACE]]는 [[로그공간 환산]]에 대해 닫혀 있다.

== 같이 보기 ==
* [[다대일 환산]]
* [[튜링 환산]]
* [[최적화 (정보 공학)|최적화]]

{{전거 통제}}

[[분류:계산 복잡도 이론]]