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 ..

Dynamic Programming 기법으로 해결할 수 있는 대표적인 문제인 LIS (Longest Increasing Subsequence) 문제입니다. 먼저 Subsequence 의 정의부터 알아보겠습니다. 길이 n인 Sequence (ordered list) S = a1, a2, ... , an 이 주어졌을 때, sequence S' = ai1, ai2, ..., aik 가 1