환산 (복잡도)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 환원의 성질
4. 환원의 종류와 응용
- 4.1. 복잡도 종류와 환원
- 4.2. 최적화 문제와 환원
5. 환원의 예시
- 5.1. 정지 문제로부터의 환원을 통한 결정 불가능성 증명 (상세 예시)
참조

1. 개요

환산은 자연수의 두 부분집합 간의 관계를 정의하며, 한 집합의 원소 판별 문제를 다른 집합의 원소 판별 문제로 변환할 수 있는지 여부를 나타낸다. 환산은 집합의 닫힘, 난해성, 완전성과 같은 개념을 정의하는 데 사용되며, 계산 복잡도 이론에서 문제의 어려움을 비교하고 분류하는 데 중요한 역할을 한다. 다대일 환산과 튜링 환산이 주로 사용되며, 문제의 결정 불가능성을 증명하는 데 활용되기도 한다.

더 읽어볼만한 페이지

계산 복잡도 이론 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
계산 복잡도 이론 - 선형 시간
선형 시간은 알고리즘의 실행 시간이 입력 크기에 비례하여 증가하는 것을 의미하며, O(n)의 시간 복잡도를 가지는 알고리즘 분석의 중요한 척도로 활용된다.

환산 (복잡도)
복잡도 이론에서의 환원
정의
목적	문제 A를 해결하기 위해 문제 B를 해결하는 방법으로, 문제 B를 해결하는 알고리즘을 문제 A를 해결하는 데 재사용할 수 있도록 하는 것
종류	다대일 환원 튜링 환원 다항 시간 환원
활용	문제의 계산 복잡도 또는 해결 불가능성을 증명하는 데 사용됨
환원 (계산 복잡성 이론)
정보
분야	계산 복잡도 이론
종류
환산 (복잡도)
개요
정의	한 문제의 해법을 다른 문제의 해법을 이용하여 찾는 것
활용	문제의 난이도를 비교 특정 문제가 다른 문제보다 '적어도 어렵다'는 것을 증명 (최악의 경우)
설명	문제 A에서 문제 B로의 환산은 문제 A를 푸는 효과적인 방법을 찾는 데 사용될 수 있음 (문제 B를 푸는 방법이 이미 알려져 있을 때) 문제 B가 풀기 '어렵다'면 문제 A도 풀기 어려움
중요성
복잡도 종류 분류	환산은 복잡도 종류를 정의하는 데 중요한 역할 (NP-완전과 같은)

2. 정의

환원(reduction)은 주어진 문제를 더 풀기 쉬운 다른 문제로 변환하는 과정이다. 환원은 주로 다음 두 가지 상황에서 사용된다.

첫째, 이미 해결한 문제와 유사한 문제를 풀려고 할 때이다. 이때 새로운 문제의 각 인스턴스를 이전 문제의 인스턴스로 변환하고, 기존의 해결책을 사용하여 해결한 다음, 이를 통해 최종 해결책을 얻을 수 있다. 이는 환원의 가장 명백한 사용 예시이다.
둘째, 해결하기 어렵다고 증명된 문제와 유사한 새로운 문제가 있을 때이다. 이때 새로운 문제를 풀기 쉽다고 가정하면, 새로운 문제의 인스턴스로 변환하여 이전 문제의 모든 인스턴스를 쉽게 해결할 수 있다는 모순을 통해 새로운 문제 또한 어렵다는 것을 보일 수 있다.

환원의 간단한 예시는 ''곱셈''에서 ''제곱''으로의 환원이다. 덧셈, 뺄셈, 제곱, 2로 나누기만 가능하다면, 다음 공식을 통해 두 숫자의 곱을 구할 수 있다.

:

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

두 숫자를 곱할 수 있다면 숫자를 제곱할 수 있으므로, 반대 방향의 환원도 가능하다. 이는 두 문제가 똑같이 어렵다는 것을 의미하는 것처럼 보인다. 이러한 종류의 환원은 튜링 환원에 해당한다.

그러나 제곱 함수를 마지막에 한 번만 사용해야 한다는 제한을 추가하면 환원은 훨씬 어려워진다. 이 경우 곱셈을 포함한 모든 기본 산술 연산을 사용할 수 있더라도, 일반적인 환원은 존재하지 않는다. 왜냐하면 제곱근을 계산해야 하는데, 이 제곱근은

\sqrt{2}

와 같은 무리수일 수 있기 때문이다. 반면, 마지막에 한 번의 곱셈으로 숫자를 제곱할 수 있다. 이러한 제한된 형태의 환원을 통해 곱셈이 일반적으로 제곱보다 어렵다는 것을 알 수 있다. 이는 다대일 환원에 해당한다.

2. 1. 환산 가능성

\mathbb N

의 두 부분집합

A

와

B

가 주어지고, 정의역과 공역이 모두

\mathbb N

이며 합성에 대해 닫힌 함수들의 집합

F

가 주어진다고 하자. 다음 조건을 만족할 때,

A

는

B

로 '''

F

에 대해 환산 가능'''하다고 한다.

:

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

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

:

A \leq_{F} B

이는 집합 A가 집합 B로 환산 가능하다는 것은, A의 원소인지 판별하는 문제를 B의 원소인지 판별하는 문제로 변환할 수 있다는 의미이다.

2. 2. 닫힘

어떤 집합 S가 환산 연산에 대해 닫혀 있다는 것은, S에 속하는 문제로 환산 가능한 모든 문제가 다시 S에 속한다는 것을 의미한다. 이를 수식으로 표현하면 다음과 같다.

:

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

여기서,

$S$ 는 자연수 집합 $\mathbb N$ 의 멱집합(모든 부분집합들의 집합) ${\color{Blue}P}(\mathbb N)$ 의 부분집합이다.
$\leq$ 는 환산 연산자이다.
$s$ 는 집합 $S$ 의 원소이다.
$A$ 는 자연수 집합의 부분집합이다.

2. 3. 난해성과 완전성

어떤 문제 A가 집합 S에 대해 난해하다는 것은, S에 있는 모든 문제가 A로 환산 가능하다는 것을 의미하며, 이는 A가 적어도 S의 모든 문제만큼 어렵다는 것을 뜻한다. 문제 A가 S에 대해 완전하다는 것은, A가 S에 속하면서 동시에 S에 대해 난해하다는 것을 의미하며, 이는 A가 S에서 가장 어려운 문제 중 하나임을 뜻한다.

구체적으로, 자연수 '''N'''의 부분집합 ''A''와 ''B''가 있고, '''N'''에서 '''N'''으로의 함수 집합 ''F''( 함수 합성에 대해 닫혀 있음)가 있을 때, 다음 조건을 만족하면 ''F''에서 ''A''가 ''B''로 '''환원 가능'''하다.

:

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

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

:

A \leq_{F} B

'''P'''('''N''')의 부분집합 ''S''가 있고, 환산을 ≤로 나타낼 때, 다음 조건을 만족하면 ≤에서 ''S''가 '''닫혀 있다'''.

:

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

'''N'''의 부분집합 ''A''는 다음 조건을 만족하면 ''S''에 대해 '''어렵다'''.

:

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

''A''가 ''S''에 대해 어렵고, 또한 ''A''가 ''S''에 포함될 경우, '''N'''의 부분집합 ''A''는 ''S''에 대해 '''완전하다'''.

3. 환원의 성질

환원은 자연수의 멱집합에 대한 전순서 관계이며, 반사 관계이자 추이 관계이다. 과거에 풀었던 문제와 매우 유사한 문제를 만나는 것은 드문 일이 아니다. 이 경우 새로운 문제를 빠르게 풀기 위해서는 새로운 문제를 과거 문제로 변환하여 기존의 해법으로 푸는 것이 좋다. 그리고 역변환을 통해 최종적인 답을 얻을 수 있다. 이것이 환원의 가장 알기 쉬운 예시이다.

다소 복잡한 사용법으로, 풀기 어렵다고 알려진 문제와 매우 유사한 문제를 받았다고 가정할 때, 새로운 문제 역시 마찬가지로 어려울 것이라고 생각할 수 있다. 여기서 역설적으로 그 새로운 문제는 쉽게 풀린다고 가정한다면, 과거 문제를 새로운 문제로 쉽게 변환(환원)할 수 있었을 때 모순이 발생한다. 즉, 새로운 문제 역시 어렵다는 것을 알 수 있다.

환원의 간단한 예시는 "곱셈"에서 "제곱"으로의 환원이다. 덧셈, 뺄셈, 제곱, 2로의 나눗셈만 알고 있다고 가정할 때, 다음 방정식을 사용하면 임의의 두 수의 곱을 구할 수 있다.

: ''a'' × ''b'' = ((a + b)² - a² - b²)/2.

역방향 환원도 가능하다. 곱셈을 알고 있다면 제곱을 계산하는 것은 쉽다. 즉, 이 두 문제의 복잡성은 동일하다. 이러한 환원은 튜링 환원과 관련이 있다.

그러나 제곱은 마지막에 1번만 할 수 있다는 제한이 추가되면 환원이 어려워진다. 이 경우 곱셈을 포함한 기본적인 연산을 모두 사용할 수 있더라도 (마지막에 제곱한다면) 환원은 불가능하다. 왜냐하면 유리수에서 $\sqrt{2}$ 와 같은 무리수를 구할 수 없기 때문이다. 역방향에서는 마지막에 반드시 곱셈을 한다는 제한이 있어도 문제없이 제곱을 구할 수 있다. 이러한 제한된 환원을 통해 곱셈 쪽이 제곱보다 더 복잡하다는 사실이 분명해진다. 이것은 다대일 환원과 관련이 있다.

4. 환원의 종류와 응용

계산 복잡도 이론에서는 주로 다대일 환산과 튜링 환산이 사용된다. 다대일 환원은 한 문제의 사례들을 다른 문제의 사례들로 변환하는 방식이다. 튜링 환원은 다른 문제를 쉽게 풀 수 있다고 가정하고 한 문제의 해답을 계산하는 방식이다. 다대일 환원은 튜링 환원보다 더 강력하며, 복잡도 클래스를 구분하는 데 더 효과적이지만, 찾기는 더 어렵다.

환원은 다음 두 가지 상황에서 주로 사용된다.

이미 해결 방법을 아는 문제와 비슷한 문제를 풀어야 할 때, 새 문제의 각 사례를 기존 문제의 사례로 변환하여 기존 해법을 적용하고, 이를 다시 원래 문제에 맞게 변환하여 해결할 수 있다.
어떤 문제를 풀기 어렵다는 것이 증명되었고, 그와 유사한 새 문제도 풀기 어려울 것이라고 예상될 때, 새 문제가 풀기 쉽다고 가정하고 모순을 유도하여 새 문제 역시 풀기 어렵다는 것을 증명할 수 있다.

곱셈과 제곱의 관계를 예로 들면, 덧셈, 뺄셈, 제곱, 2로 나누기만 가능하다면, ''a'' × ''b'' = ((a + b)² - a² - b²)/2 공식을 통해 두 수의 곱을 구할 수 있다. 이는 튜링 환원에 해당한다.

하지만 제곱 연산을 마지막에 한 번만 사용해야 한다면, 곱셈을 포함한 다른 연산은 모두 사용 가능해도 일반적인 환원은 불가능하다. 제곱근을 구해야 하는데, 그 결과가 무리수일 수 있기 때문이다. 반면, 마지막에 곱셈을 한 번만 사용하는 것은 가능하다. 이를 통해 곱셈이 제곱보다 더 어렵다는 것을 알 수 있으며, 이는 다대일 환원에 해당한다.

어떤 문제가 특정 복잡도 종류에 대해 완전하다는 것은, 해당 종류 내의 모든 문제가 그 문제로 환원될 수 있고, 그 문제 자체가 해당 종류에 속한다는 것을 의미한다. 이러한 의미에서 완전한 문제는 그 종류를 대표한다고 할 수 있다.

4. 1. 복잡도 종류와 환원

P, NP, PSPACE 등의 복잡도 종류는 다항 시간 환원에 대해 닫혀 있다. L, NL, P, NP, PSPACE 등의 복잡도 종류는 로그 공간 환원에 대해 닫혀 있다.

계산 복잡도에서 사용되는 주요 환산 유형에는 다대일 환산과 튜링 환산이 있다. 다대일 환산은 한 문제의 ''사례''를 다른 문제의 ''사례''로 매핑하는 반면, 튜링 환산은 다른 문제를 쉽게 해결할 수 있다고 가정하여 한 문제에 대한 해답을 ''계산''한다. 다대일 환산은 튜링 환산보다 강력한 유형이며 문제를 별개의 복잡도 클래스로 구분하는 데 더 효과적이다. 그러나 다대일 환산에 대한 제약이 증가함에 따라 찾기가 더 어려워진다.

어떤 문제가 특정 복잡도 클래스에 대해 완전하다는 것은, 해당 클래스 내의 모든 문제가 그 문제로 환원될 수 있고, 그 문제 자체가 해당 클래스에 속한다는 것을 의미한다. 이러한 의미에서 완전한 문제는 그 클래스를 대표한다고 할 수 있다. 왜냐하면 완전한 문제에 대한 해법은, 환산을 통해 그 클래스의 모든 문제를 해결하는 데 사용될 수 있기 때문이다.

하지만 환산은 ''쉬워야'' 실질적인 의미를 가진다. 예를 들어, 풀기 어려운 NP-완전 문제인 불만족 문제를, 어떤 수가 0인지 아닌지를 판별하는 것과 같이 매우 쉬운 문제로 환원하는 것은 가능하다. 환산하는 과정에서 지수 시간이 걸리더라도, 해가 존재할 때만 0을 출력하게 만들면 되기 때문이다. 그러나 이러한 환산은, 새로운 문제를 해결하는 것만큼이나 어렵기 때문에 실용적이지 않다. 마찬가지로, 계산 가능한 함수를 계산하는 환산은 결정 불가능 문제를 결정 가능한 문제로 환원할 수도 있다. 마이클 시프서는 그의 저서 ''계산 이론 입문''에서 "환산은 해당 클래스에서 일반적인 문제의 복잡성에 비해 쉬워야 한다[...] 만약 환산 자체를 계산하기 어렵다면, 완전 문제에 대한 쉬운 해법이 거기에 환산되는 문제에 대한 쉬운 해법을 반드시 생성하지는 않을 것이다."라고 지적했다.

따라서 적절한 환산의 개념은 어떤 복잡도 클래스를 다루느냐에 따라 달라진다. NP나 다항식 계층과 같이 더 어려운 복잡도 클래스를 연구할 때는 다항 시간 환산을 사용한다. 반면, P 내부에 있는 NC나 NL과 같은 클래스를 연구할 때는 로그 공간 환산을 사용한다.

4. 2. 최적화 문제와 환원

최적화 문제에서는 근사 보존 환산을 통해 한 문제의 근사 해법을 다른 문제의 근사 해법으로 변환할 수 있다. 두 최적화 문제가 있을 때, 한 문제의 인스턴스를 다른 문제의 인스턴스로 매핑하고, 후자의 문제에 대한 거의 최적의 해법을 다시 변환하여 전자의 거의 최적의 해법을 얻을 수 있다고 가정한다. 이러한 방식으로, 문제 B에 대한 거의 최적(또는 최적) 해법을 찾는 알고리즘(근사 알고리즘 포함)과 문제 A에서 문제 B로의 효율적인 근사 보존 환산이 있다면, 이를 통해 문제 A에 대한 거의 최적의 해법을 생성하는 알고리즘을 얻을 수 있다.

근사 보존 환산은 근사 경도 결과를 증명하는 데 사용될 수 있다. 예를 들어 어떤 최적화 문제 A가 어떤 α에 대해 α보다 나은 요인 내에서 근사하기 어렵고(어떤 복잡도 가정 하에서), 문제 A에서 문제 B로의 β 근사 보존 환산이 있다면, 문제 B는 α/β 요인 내에서 근사하기 어렵다고 결론지을 수 있다.

5. 환원의 예시

환원은 이미 해결된 문제를 이용하여 유사한 문제를 해결하거나, 어떤 문제가 풀기 어렵다는 것을 증명하는 데 사용된다.

유사 문제 해결: 이미 해결 방법을 알고 있는 문제와 비슷한 새로운 문제를 만났을 때, 새로운 문제를 기존 문제로 변환하여 해결할 수 있다. 예를 들어, 새로운 문제의 각 사례를 이전 문제의 사례로 바꾸고, 기존 해결책을 적용한 후, 이를 다시 원래 문제의 해결책으로 변환하는 것이다.
난이도 증명: 어떤 문제가 풀기 어렵다는 것을 증명하고 싶을 때, 이미 풀기 어렵다고 알려진 문제에서 해당 문제로 환원할 수 있음을 보인다. 만약 새로운 문제가 풀기 쉽다고 가정하면, 기존의 어려운 문제도 쉽게 풀 수 있다는 모순이 발생한다. 따라서 새로운 문제 역시 풀기 어렵다는 결론을 내릴 수 있다.

간단한 예로, '곱셈'을 '제곱'으로 환원하는 경우가 있다. 덧셈, 뺄셈, 제곱, 2로 나누기만 가능하다면, 다음 공식을 통해 두 수의 곱을 구할 수 있다.

: ''a'' × ''b'' = ((a + b)² - a² - b²)/2

반대로, 곱셈을 할 수 있다면 제곱도 쉽게 계산할 수 있다. 이는 두 문제가 비슷한 난이도를 가진다는 것을 보여준다. 이러한 환원은 튜링 환원과 관련이 있다.

하지만 제곱을 마지막에 한 번만 사용해야 한다는 제약이 있다면, 곱셈을 포함한 다른 모든 연산을 사용할 수 있어도 환원이 불가능하다. 왜냐하면 제곱근을 구해야 하는데, 제곱근 중에는 무리수가 있어 유리수 연산만으로는 구할 수 없기 때문이다. 반면, 곱셈을 마지막에 한 번만 사용해서 제곱을 하는 것은 가능하다. 이러한 제한된 환원을 통해 곱셈이 제곱보다 어렵다는 것을 알 수 있다. 이는 다대일 환원과 관련이 있다.

어떤 결정 문제가 결정 불가능 문제임을 보이기 위해서는, 이미 결정 불가능하다고 알려진 문제에서 해당 문제로의 계산 가능한 함수를 이용한 환원을 찾는다. 예를 들어, 정지 문제가 특정 문제로 환원됨을 보여 그 문제가 결정 불가능함을 증명하는 방법이 자주 사용된다.

복잡도 종류 P, NP, PSPACE는 다항 시간 환원에 닫혀 있고, L, NL, P, NP, PSPACE는 로그 공간 환원에 닫혀 있다.

5. 1. 정지 문제로부터의 환원을 통한 결정 불가능성 증명 (상세 예시)

다음 예시는 정지 문제로부터의 환원을 사용하여 특정 언어가 결정 불가능함을 증명하는 방법을 보여준다.

주어진 튜링 기계 ''M''이 입력 문자열 ''w''에서 (수락 또는 거부로) 멈추는지 여부를 결정하는 문제를 ''H''(''M'', ''w'')라고 하자. 이 언어는 결정 불가능한 것으로 알려져 있다. 주어진 튜링 기계 ''M''이 허용하는 언어가 비어 있는지 (다시 말해, ''M''이 어떤 문자열이라도 허용하는지)를 결정하는 문제를 ''E''(''M'')이라고 하자. 우리는 ''H''로부터의 환산을 통해 ''E''가 결정 불가능함을 보인다.

모순을 얻기 위해 ''E''에 대한 결정자 ''R''이 있다고 가정한다. 우리는 이것을 사용하여 ''H''에 대한 결정자 ''S''를 생성한다 (우리는 그러한 것이 존재하지 않는다는 것을 알고 있다). 입력 ''M''과 ''w''(튜링 기계와 일부 입력 문자열)이 주어지면, ''S''(''M'', ''w'')는 다음과 같이 동작한다. ''S''는 입력 문자열이 ''w''이고 ''M''이 입력 ''w''에서 멈추는 경우에만 허용하고, 그렇지 않으면 멈추지 않는 튜링 기계 ''N''을 생성한다. 이제 결정자 ''S''는 ''R''(''N'')을 평가하여 ''N''이 허용하는 언어가 비어 있는지 확인한다. ''R''이 ''N''을 허용하면, ''N''이 허용하는 언어는 비어 있으며, 따라서 특히 ''M''은 입력 ''w''에서 멈추지 않으므로 ''S''는 거부한다. ''R''이 ''N''을 거부하면 ''N''이 허용하는 언어는 비어 있지 않으며, 따라서 ''M''은 입력 ''w''에서 멈추므로 ''S''는 허용한다. 따라서 ''E''에 대한 결정자 ''R''이 있다면, 우리는 어떤 기계 ''M''과 입력 ''w''에 대해서도 정지 문제 ''H''(''M'', ''w'')에 대한 결정자 ''S''를 생성할 수 있을 것이다. 우리는 그러한 ''S''가 존재할 수 없다는 것을 알고 있으므로, 언어 ''E''도 결정 불가능하다는 결론을 얻는다.

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com