[Algorithm] Reduction for Decision Problem

Decision Problem 에 Reduction 을 적용하는 사례들에 대해 살펴보도록 하겠습니다.

 

두 Decision Problem X, Y 에 대해 다음과 같은 관계가 존재하는 경우, X is reducible to Y 라고 할 수 있습니다.

1. 임의의 X의 Instance Ix 를 2번을 만족하는 Y의 Instance Iy 로의 변환이 가능해야합니다.
2. Instance Iy 에 대한 Y의 답을 이용하여 Instance Ix 에 대한 X의 답을 구할 수 있어야 합니다. Decision Problem 인 경우에 한하여 두 답은 언제나 동일해야 합니다. ( Ix 에 대한 X의 답 <=> Iy 에 대한 Y의 답 (if and only if 로 양방향으로 같다는 것을 증명해야합니다.) )

 

X가 Y로 reducible 한 경우에, X의 instance 를 Y의 instance로 바꾸는 algorithm 을 X에서 Y로의 Reduction 이라고 합니다.

 

두 Decision Problem X에서 Y로의 reduction R 이 주어지고, problem Y를 해결하는 Algorithm Ay 가 주어질 경우, problem X를 해결하는 Algorithm Ax 를 다음과 같이 디자인 할 수 있습니다.

 

1. Reduction R 을 이용하여 X 의 instance Ix 를 Y의 Instance Iy 로의 변환을 수행합니다.
2. Instance Iy 에 대한 답을 Ay 를 통해 구합니다.
3. 2에서 구한 답이 Ix 에 대한 답이 됩니다.

X <= Y 일 때 (X is reducible to Y), X를 해결하는 Algorithm Design

R과 Ay 가 모두 polynomial time complexity 를 갖는 Algorithm 이라면 Ax 또한 Polynomial Time Complexity 를 갖습니다. (O(n^d)의 덧셈 연산이므로 당연합니다.)

 

X <= Y 가 성립하는 경우, X를 해결하는 것은 Y를 해결하는 것보다 절대로 어려울 수 없습니다. 다른 말로 Y를 해결하는 것은 적어도 X를 해결하는 것만큼 어렵습니다. 왜 그럴까요?

 

X를 해결하는 Algorithm Ax 가 존재하고 Ix를 Iy로 Convert 할 수 있는 Alogrithm R이 존재하더라도, Iy 를 해결하는 Algorithm Ay 의 존재성을 확정할 수 없기 때문입니다.

 

예를 들어, Problem X : 길이 k 이상의 LIS 존재 여부를 판별하는 문제이고 Problem Y : DAG 에서 Longest Path 의 길이가 k 이상인지를 판별하는 문제라고 합시다.

 

X <= Y 이므로, Y를 해결하는 것은 적어도 X를 해결하는 것만큼 어렵습니다.

이 문제에 대해서는 Y <= X도 성립합니다. X <= Y이므로 Ix에 대한 X의 답과 Iy 에 대한 Y의 답은 서로 같음이 보장되고, Iy 는 topology Sort 를 통해 Ix로 convert 할 수 있기 때문입니다.