[Algorithm] Polynomial-Time Reduction

어떤 Algorithm 이 polynomial - time 에 동작하는 경우 즉, O(n^d) 에 동작하는 경우에 해당 알고리즘을 보통 Effecient Algorithm 이라고 합니다.

 

보통의 경우, 어떤 문제를 해결하는 Efficient Algorithm 을 찾기 위해서는 그 문제를 polynomial time 에 동작하는 reduction 이 가능한지를 생각하며, 이를 polynomial-time reduction 이라고 합니다.

 

Polynomial Time Reduction 의 정의를 살펴보겠습니다.

 

Definition of Polynomial Time Reduction

Decision Problem X 에서 Decision Problem Y 로의 Polynomial Time Reduction 은 다음의 성질들을 만족하는 Algorithm R 을 의미합니다.

1. 임의의 X의 Instance Ix 에 대해 R은 Y의 instance Iy 를 반환합니다.
2. | Iy | (Instance of Y 의 size) = poly(|Ix|) ( = Ix^d)
3. R은 |Ix| 에 대해 Polynomial time 에 동작합니다. (3번은 2번을 내포합니다.)
4. Ix 는 문제 X에 대해 YES 를 출력하는 instance 이면 Iy 는 문제 Y에 대해 YES 를 출력하는 instance여야 합니다. (if and only if 가 성립해야함)

 

Polynomial-time Reduction과 관련한 특성들을 살펴보도록 하겠습니다.

 

문제 X 에서 Y 로의 polynomial-time reduction 이 존재하는 경우 ( = X is reducible to Y in polynomial time complexity) 이를 X <= pY 로 표기하며, X <= pY 이고, Y를 해결하는 polynomial-time Alogrithm Ay 가 존재한다면, 문제 X를 해결할 수 있는 polynomial time algorithm Ax도 존재합니다. ( Reduction Alogrithm R 과 Ay를 linear 하게 더한 알고리즘을 통해 X를 해결할 수 있으므로 당연합니다.)

 

이전 포스팅에서 다루었던 Indepedent Set and Clique 문제를 생각하며 다음의 명제들을 살펴보겠습니다.

 

Graph G 를 이용해 G의 complement G' 을 polynomial time 안에만들 수 있으므로 ( Reduction Algorithm R = O(n^d) ),

Independent Set <= p Clique 임을 알 수 있습니다.

 

Independent Set <= p Clique 일 때 만약 Independent Set 을 해결하는 efficient algorithm 이 존재하지 않는다면, Clique 를 해결하는 efficient algorithm 또한 존재하지 않습니다.

 왜냐하면, clique 을 해결하는 efficient algorithm 이 존재한다면 Indepedent Set <= p Clique 이므로 Instance of X 를 Instance of Y를 polynomial time 에 만들 수 있으므로, Independent Set 문제를 해결하는 efficient algorithm 이 없다는 가정에 모순됩니다. (Contradiction!)

 

따라서, X <= p Y 이고, X를 해결하는 efficient algorithm Ax 이 존재하지 않는다면, Y를 해결하는 polynomial time Algorithm Ay도 존재하지 않습니다.