어떤 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 은..

그래프 G(V,E) 의 Independent Set 을 구하는 문제는 Cliques 를 구하는 문제로 reduction 할 수 있습니다. 먼저 Indepedent Set 과 Clique 의 정의에 대해 알아보도록 하겠습니다. Definition of Indepedent Set Graph G(V, E) 에 대해 Vertex set V’ ⊂ V 에 속한 모든 vertex 들이 서로 adjacent 하지 않으면 V’ 은 G 의 independent set 입니다. ( ∀ i, j ∈ V', (i, j) ∉ E 이면 V' 은 그래프 G의 Indepedent Set ) Definition of Clique Graph G(V, E)에 대해 Vertex set V’ ⊂ V 에 속한 모든 vertex 들이 서로 adj..

Decision Problem 에 Reduction 을 적용하는 사례들에 대해 살펴보도록 하겠습니다. 두 Decision Problem X, Y 에 대해 다음과 같은 관계가 존재하는 경우, X is reducible to Y 라고 할 수 있습니다. 임의의 X의 Instance Ix 를 2번을 만족하는 Y의 Instance Iy 로의 변환이 가능해야합니다. Instance Iy 에 대한 Y의 답을 이용하여 Instance Ix 에 대한 X의 답을 구할 수 있어야 합니다. Decision Problem 인 경우에 한하여 두 답은 언제나 동일해야 합니다. ( Ix 에 대한 X의 답 Iy 에 대한 Y의 답 (if and only if 로 양방향으로 같다는 것을 증명해야합니다.) ) X가 Y로 reducible ..

Reduction 이란 문제 X와 문제 Y가 있을 때 문제 Y를 해결하는 알고리즘 Ay 가 존재한다고 할 때, Ay 를 이용하여 문제 X를 해결하는 알고리즘 Ax 를 디자인 할 수 있는 경우 문제 X에서 Y로 reduction 이 가능하다 (X is reducible to Y)고 이야기합니다. (Strict 한 정의는 아닙니다.) 그리고 X에서 Y로의 reduction 이 가능함을 X