12. Reductions

1. Introduction

 

Reduction이란 다음을 의미한다.

If you can use an algorithm that solve Y to help solve X, Problem X reduces to problem Y

즉, 문제 X를 문제 Y를 푸는데 사용한 알고리즘을 활용해 해결할 수 있으면, 문제 Y로 축소된다고 보는 것이다.

 

우리는 문제 X에 대한 인스턴스를 문제 Y에 대한 인스턴스로 변환(preprocessing)하고, 알고리즘으로 해결한 후, 다시 결과를 변환(postprocessing)시킨다.

따라서 문제 X를 해결하는 총 비용은, 문제 Y를 해결하는 비용 + Reduction 비용이다.

 

예를 들어, N개의 item에 대한 중간값을 구한다고 해보자.

Preprocessing없이, 바로 정렬을 시도할 수 있다. cost = NlogN이다.

정렬된 결과로 중간 인덱스 값을 찾는다(Postprocessing). cost = 1 이다.

따라서, 총 비용은 NlogN + 1이다.

 

2. Designing algorithms

 

우리는 알고리즘을 디자인할 때, reduction을 활용할 수 있다.

 

Convex Hull problem을 보자.

y좌표가 가장 작은 점을 기준으로 polar angle을 계산해 그것을 sorting한다. 그리고 그것을 바탕으로 point를 하나씩 거쳐가며 탐색하면서 convex hull을 완성시킨다.

cost는 sorting problem cost + reduction인데,

sorting시간이 NlogN이고, preprocessing은 polar angle계산까지의 과정이고 총 N개의 점에 대해서 각각 계산되므로 N이다. postprocessing은 N개의 점을 한번씩 탐색하며 convex hull을 완성시키므로 총 N이다.

따라서 reduction의 cost는 ~N이다.

전체 cost = NlogN + N 일 것이다.

 

Undirected graph에서 Shortest path를 구하는 문제를 보자.

이것은 Digraph의 shortest path를 구하는 알고리즘을 이용해 구할 수 있다.

Undirected graph를 양방향 Edge로 변환한 후, 알고리즘을 시행하면 된다. Reduction은 Edge를 변환하는데 드는 비용인 N이다. Shortest path의 cost가 ElogV이므로, 전체 cost = ElogV + V 일 것이다.

다만, edge의 weight가 음수가 있는 경우에는 주의해야하는데, 음수 사이클이 발생하기 때문이다.

 

3. Establishing lower bounds

 

우리가 알고리즘 초반에서 보았듯이, lower bound를 증명하는 것은 쉽지 않은 일이다. 하지만 이것을 알면, 어디까지 개선이 가능하고 더이상 개선 불가능한지 여부를 판단할 수 있기 때문에 매우 유용하다. 

 

만약, Problem X, Problem Y가 있을 때,

Problem X가 Linear number of standard computational step, Constant number of calls to Y 로 해결된다면,

Problem X linear-time reduces to problem Y 라고 한다. 

 

그리고 이럴 경우, problem X의 lower bound가 NlogN이라면, problem Y의 lower bound도 NlogN이 된다.

problem X의 lower bound가 N^2이라면, problem Y의 lower bound도 N^2이 된다.

이러한 방식으로, 특정 문제의 lower bound로 이용한 알고리즘의 lower bound를 결정할 수 있다.

이것은 X를 쉽게 풀 수 없다면 Y도 쉽게 풀 수 없다는 의미가 된다.

 

예를 들어, convex hull을 생각해보자.

우리는 이전에 convex hull을 sorting으로 해결했는데, 역으로 sorting을 convex hull방법으로 해결할 수 있다.

따라서, Sorting linear-time reduces to convex hull 이다.

Sorting의 lower bound는 NlogN이 증명되었으므로, convex hull의 lower bound도 NlogN이 된다.

 

4. Classifying problems

 

Sorting linear-time reduces to convex hull 이고, convex hull linear-time reduces to Sorting 이다.

이런 경우, 우리는 두 문제는 같은 complexity를 갖는다고 한다.

따라서, 두 문제는 같은 class의 problem으로 분류될 수 있다.

 

Nbit가 주어졌을 때, 곱하기 연산을 생각해보자.

Brute-force알고리즘을 사용하면, N^2의 시간이 걸린다.

그런데, 나눗셈, 제곱, 제곱근을 구하는 것 모두 곱하기 연산으로 linear time reduce될 수 있고. 반대도 성립한다.

따라서, 곱셈, 나눗셈, 제곱, 제곱근 문제 모두 same complexity를 같는 같은 class의 문제라고 볼 수 있다.

이렇게 class를 나누는 이유는, 바로 한 문제를 효율적으로 풀면 같은 클래스 내 다른 문제도 효율적으로 풀리기 때문이다.

 

한가지 안타까운 사실은, 이렇게 class로 분류되지 않은 복잡도를 가진 문제들이 있다는 것이다. 그것은 다음에 살펴볼 것이다.