[Algorithm] Reduction
Reduction 이란 문제 X와 문제 Y가 있을 때 문제 Y를 해결하는 알고리즘 Ay 가 존재한다고 할 때, Ay 를 이용하여 문제 X를 해결하는 알고리즘 Ax 를 디자인 할 수 있는 경우 문제 X에서 Y로 reduction 이 가능하다 (X is reducible to Y)고 이야기합니다. (Strict 한 정의는 아닙니다.) 그리고 X에서 Y로의 reduction 이 가능함을 X <= Y 라고 표기합니다. (Notation)
다음과 같은 경우들에 Reduction 을 사용합니다.
- 특정 문제를 해결하는 Alogrithm 을 디자인할 때 사용합니다.
- 어떤 문제를 해결하는 Algorithm 이 존재하지 않는 것 ( 혹은 매우 해결하기 어려움 ) 을 증명하기 위해 사용합니다.
주로 2번째 Case 에 Reduction 을 사용합니다.
Reduction에 대한 자세한 설명에 앞서 Reduction 과 관련한 몇가지 용어에 대한 정의부터 짚어봅시다.
먼저 "문제(Problem)" 을 어떻게 정의할 수 있을까요? 문제를 정의하기위해 필요한 용어 하나에 대해 알아보겠습니다.
Definition of Problem Instance
우리가 문제를 푼다라고 이야기 하는 것은 어떤 Input 에 대해 문제를 해결하는 Algorithm 을 적용하여 답을 얻는 행위를 의미합니다. 이 때, 어떤 Problem 을 정의하는 "Input" 을 Problem Instance라고 합니다.
Definition of Problem
그리고 Problem 이란 '특정 조건을 만족하는 problem instance' (valid 한 input) 들의 set으로 정의할 수 있습니다.
따라서 Problem 과 Problem Instance 는 다릅니다.
다음으로, Problem 의 종류 중 일부분에 대해 알아보겠습니다.
Type of Problem
- Decision Problem : 답이 YES / NO 로 도출되는 문제를 이야기합니다. ~의 존재 유무를 밝히는 문제가 대표적입니다.
- Search Problem : 특정 조건을 만족하는 Solution 을 찾는 문제를 이야기합니다. 예를 들어 'Array 에서 3이상의 모든 element 를 찾아라' 와 같은 문제가 Search Problem 입니다.
- Optimization Problem : 여러개의 선택가능한 후보들 중 최적의 해(e.g., Maximum, Minimum etc...) 를 찾는 문제를 이야기합니다. 예를 들어, LIS 와 같은 문제가 Optimization Problem 입니다.
간단한 예시를 통해 Reduction 이 무엇인지 이해해보도록 하겠습니다.
문제 X : Selection (Size 가 n인 Array[1, ... , n] 이 존재할 때 k번째로 작은 element 찾기)
문제 Y : Sorting (Size가 n인 Array[1, ..., n]이 존재할 때 Array를 non-decreasing order 로 sorting)
문제 X와 Y의 Input 은 서로 같습니다. 그리고 문제 Y를 해결하는 알고리즘을 이용함으로써 문제 X를 해결하는 알고리즘을 디자인 할 수 있습니다. (Selection은 Sorting 후 index k 의 element 를 return 하면 해결가능함)
따라서 'Selection 은 Sorting 으로의 Reduction 이 가능하다', 'Selection 에서 Sorting으로의 reduction이 존재한다' 라고 말할 수 있습니다.