[Algorithm Part 2] 11. Reduction

이번 글에서 reduction과 그로 인해 얻을 수 있는 3가지 요소에 대해 살펴볼 것이다.

---

1. Algorithm design

Definition

Problem $X$ reduces to problem $Y$, if you can use an algorithm that solves $Y$ to help solve $X$.
 
Cost of solving $X$ = total cost of solving $Y$ + cost of reduction(=preprocessing and postprocessing)
 
정렬 알고리즘을 통해 중앙값 알고리즘을 얻을 수 있던 것처럼,

reduction은 "기존 문제의 알고리즘으로 다른 문제의 알고리즘 설계에 도움을 주는 개념"이다.
때문에, 새로운 문제를 만났을 때, 새로운 알고리즘을 설계하기 보단, 기존 알고리즘으로 풀 수 있는지 확인해봐야 한다.

---

Example: 1. Convex hull reduces to sorting

Graham scan 알고리즘을 활용하면 reduction이 가능하다. 즉, 정렬 알고리즘을 통해 convex hull를 풀 수 있다.

Graham scan algorithm

• y좌표가 가장 낮은 점 p를 찾는다.
• 점 p와의 극각을 기반으로 점들을 정렬한다.
• 정렬 순서대로 점들을 방문하면서, 다음 조건을 만족할 경우 선에 점을 추가한다.
  (선과 방문한 점을 잇고, 이가 반시계 방향으로 회전할 경우 선에 추가한다.)
  위 조건은 "시계 방향으로 회전할 경우 convex hull이 되지 못함"을 의미한다.

cost of convex hull: $N\log N$(cost of sort) + $N$(cost of reduction)

Example: 2. Undirected shortest paths reduces to directed shortest path

무방향 간선을 양방향 간선으로 변경하면 reduction이 가능하다.

cost of undirected shortest paths: $E \log V$(cost of shortest paths in digraph) + $E$(cost of reduction)

---

예시처럼, reduction으로 핵심적인 problem solving model 사용해 여러 가지 종류의 문제를 풀 수 있다.

Application of problem A(e.g., sorting) means problem reduce to A!!

---

2. Establishing lower bound

문제의 lower bound를 증명하는 과정은 매우 어렵다.

하지만, reduction을 활용하면 보다 쉽게 증명할 수 있다.

Definition

Problem X linear-time reduces to problem Y if X can be solved with:

• Linear number of standard computational steps
• Constant number of calls to Y

Step

만약, 1). X의 lower bound을 알고, 2). X linear-time reduces to Y할 경우, Y의 lower bound는 X의 lower bound다.

즉, X의 lower bound보다 빠른 Y의 알고리즘이 존재하지 않는다.

Proof

만약 X의 lower bound보다 빠른 알고리즘이 존재한다고 가정할 경우,

(가정2로 인해) X를 X의 lower bound보다 더 빨리 풀 수 있는 알고리즘이 존재한다.

하지만, 이는 가정1과 모순되기에, 성립하지 않는다. 그렇기에, 존재하지 않는다.

---

Example: Lower bound of Convex Hull

Sorting linear-time reduces to convex hull

 

Proof

Sorting instance가 $x_1, x_2, \cdot, x_n$이라고 할 때,

convex hull instance를 $(x_1, {x_1}^2), (x_2, {x_2}^2), \cdots, (x_n, {x_n}^2)$라고 둘 수 있다.

이때, convex hull의 모든 점은 $\{x: x^2 \ge x\}$이기에, 모든 점이 convex hull에 포함된다.

convex hull의 알고리즘은 최대 음수 $x$부터 시계 반대 방향 순서대로 방문을 하는데, 이는 오름차순 순서와 같다.

때문에, convex hull 알고리즘을 통해, sorting 결과값을 얻을 수 있다.

---

Reduction은 lower bound를 구하는데 사용되는 매우 유용한 tool이다.

 

"linear-time convex hull 알고리즘이 존재하지 않는 것"을 증명하는 방법에는 2가지가 있다.

1. hard: 백지에서 linear-time 알고리즘이 없다는 것을 증명하는 것 
2. easy: "sorting linear-time reduces to convex hull임"을 보이는 것 

---

3. Classifying Problems

문제 난이도(difficulty = complexity)에 따른 분류 방법에 대해 고찰해볼 필요가 있다.

이전까지는 lower bound가 증명된 문제만 분류했다. 

Reduction은 lower bound가 증명되지 않은 문제들도 포함한 분류 방법을 제시한다.

 

Two problems X and Y have the same complexity

1. If problem X linear-time reduces to Y
2. If problem Y linear-time reduces to X

X 혹은 Y의 lower bound를 몰라도, "complexity는 같다"는 것을 알 수 있다.

 

reduction이 없을 때는, lower bound가 증명되지 않은 문제의 difficulty의 표현 방법은 가장 optimal한 algorithm의 time-complexity였다.

하지만 reduction이 활용하면, lower bound를 몰라도, 위 방법으로 complexity가 같은 문제들을 묶어 difficulty를 표현할 수 있게 되었다.

---

Example

1. lnteger multiplication

여러 정수 연산은 정수 곱에 reduce된다. (other integer operations reduces to integer multiplication)

즉, 정수 산술 문제는 같은 complexity를 가지고 있다.

 

2. Matrix multiplication

여러 선형대수 산술 문제는 행렬 곱에 reduce된다.

(numerical linear algebra problems with the same complexity as matrix multiplication)