Polynomial-Time Reductions

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Polynomial-Time Reductions

만약, Problem X가 polynomial-time에 풀 수 있는 알고리즘을 가지고 있다 하자. 그리고 problem Y는 이 알고리즘을 이용하여 풀 수 있다면 Problem Y는 polynomial-timem reducible 이다. 아래와 같이 기호로 표기한다.

 

$Y \le_P X$

 

X가 poly-time으로 풀린다면 Y 또한 poly-time으로 해결된다. 이는 문제의 상대적 어려움을 뜻한다.

 

$Y \le_P X$ 이고, $X \le_P Y$ 이면, $X \equiv_P Y$로 표시한다.

 

 

 

Claim

VERTEX-COVER $\equiv_P$ INDEPENT-SET

 

INDEPENT-SET : Subset안의 임의의 vertex 두개를 잡았을 때, 연결된 edge가 없는 maximal subset을 찾는 문제 

VERTEX-COVER : Subset안의 모든 vertex의 인접한 edge를 모두 찾았을 때 전체 edge를 cover할 수 있는 minimal subset을 찾는 문제

 

 

 

Pf ) Show S is an independent set iff V-S is a vertex cover

 

1. VERTEX-COVER $\le_P$ INDEPENDENT-SET

$S$를 independent set이라 하자. edge $(u, v)$가 있을 때, $u \notin S$ 또는 $v \notin S$이다.

둘 중 모두 S에 들어가면 independent set이 되지 않는다.

$u \notin S$ or $v \notin S$ $\Rightarrow$ $u \in V-S$ or $v \in V-S$

따라서 $V-S$는 $(u, v)$를 cover한다.

 

2. VERTEX-COVER $\ge_P$ INDEPENDENT-SET

$V-S$를 vertex cover라 하자.

$u \in S,  v \in S$\라 둘 때, $(u, v) \notin E$이다. 

만약 $(u, v)$가 존재하면 $V-S$가 그 edge를 cover하지 못하기 때문에 vertex cover라는 가정에 모순이다.

$S$의 vertex 사이의 edge가 존재하지 않으므로 $S$는 independent set이다.

 

 

SET-COVER : graph U에 해당하는 여러개의 subset들이 있을 때, 최소 개수의 subset을 이용해서 전체를 cover하는 문제이다.

 

Claim

VERTEX-COVER $\le_P$ SET-COVER

 

Pf )

아래 그림처럼 graph에서 모든 노드에 대해 연결되어 있는 edge를 subset으로 묶자. 그리고 해당 subset들에 대해 set cover문제를 풀면 vertex cover를 구할 수 있다.

 

 

 

 

 

Reduction via Gadgets

SAT 문제 (Satisfiability Problem)

: CNF (Conjunctive normal form)가 주어졌을 때, 이를 참으로 만드는 assginment를 구하는 문제이다.

 

 

각 clause가 정확히 3개의 literal를 가지고 있으면 3-SAT문제라고 한다.

 

 

Claim

3-SAT $\le_P$ INDEPENDENT-SET

 

Pf ) 

CNF를 아래의 그래프 형태로 설계할 수 있다.

 

 

 

 

같은 clause 내에서는 삼각형으로 연결하고, $x, \bar{x}$\끼리 edge로 연결한다. 이 그래프에 대해 independent set을 구하면 해당되는 노드들이 3-SAT 문제의 결과물이다.

 

 

Claim

G는 size $k = |\Upsilon|$인 independent가 존재 iff $\Upsilon$ is satisfiable

 

1. $\Rightarrow$

삼각형 내에서는 무조건 1개만 선택되어야하고 $x, \bar{x}$는 서로 assign 불가하므로 CNF를 참으로 만든다.

 

2. $\Leftarrow$

삼각형 마다 assign이 1개되므로 independent set의 크기는 k이다.

 

 

지금까지의 정리로 다음과 같은 관계가 성립한다.

 

3-SAT $\le_P$ INDEPENDENT-SET $\le_P$ VERTEX-COVER $\le_P$ SET-COVER

 

 

Self-Reducibility

Search problem $\le_P$ Decision problem

 

input size가 polynomial일 때, Decision problem을 여러번 반복하면 Search problem을 풀 수 있으므로, 위의 관계가 성립한다. 즉, decision 문제가 search 문제보다 더 쉽다는 것을 의미한다. Decision problem이 poly-time이라면 Search problem또한 poly-time이 된다.