中庸 中庸

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

어떤 문제를 해결하는 데 걸리는 소요시간의 lower bound 를 찾는 방법 중의 하나인 방해꾼 논법에 대해 알아보겠습니다. 방해꾼 논법 (Adversary Argument) 1. 해결하는 사람 (Solver) 와 상대방 (Adversary) 간의 일종의 스무고개 같은 게임입니다. 2. Adversary 는 input 을 가지고 있고, solver 는 input 이 무엇인지 확인할 수 없습니다. 3. solver는 adversary 에게 질문을 할 수 있습니다. 이 때, 질문은 형식에 맞춰 질문해야 합니다. ( 알고리즘의 계산 모델 제약 조건이 질문의 형식 제약이라고 생각할 수 있습니다. ) 4. adversary는 solver 의 질문에 대해 답변을 해주어야 합니다. 이 때, solver 가 최대한 ..

해결 가능한 어떤 문제가 주어져 있다고 했을 때, 이 문제를 해결하는 algorithm 의 upper bound 와 lower bound 를 어떻게 정의할 수 있을까요? 먼저 Upper Bound 에 대해 알아봅시다. 해결 가능한 어떤 문제를 T 시간 안에 해결하는 algorithm 이 존재한다. 해당 문제를 해결하는 algorithm 의 upper bound 가 T 이다. 이 두 명제는 서로 동치입니다. 그렇다면, 의미없지만 당연한 예시로 size 가 n 인 array 를 sort 하는 문제는 O(n^100) 으로 해결할 수 있을 것이고, O(n^90) 으로도 해결할 수 있을 것입니다. 그렇기 때문에 Upper Bound 간 우열이 존재합니다. 더 짧은 시간 안에 문제를 해결하는 것이 우수하다고 생각하..