mojo's Blog

Integer partitioning 어떻게 해결해야 할지에 대한 접근법을 들어보자. 1. Greedy strategy 예를 들어 S = {4, 5, 6, 7, 8} 가 있을 때, Greedy strategy 로는 solution을 찾을 수 없다. 2. Dynamic programming To solve an instance of subset sum, need to calculate f(1, t). Note that f(j, t) = f(j + 1, t) or f(j + 1, t - xj). The boundary condition is f(l, t) = true if t = 0 or t = xl and false otherwise. The running time is propotional to the ..

Theorem 1 A 2-sat formula φ is satisfiable if and only if there is no variable x with paths from x ~> x' and x' ~> x in G(φ). Proof : If such a pair of paths exists, then φ is contradictory, and hence unsatisfiable. Suppose then that no such pair exists. Observe that a single one of these paths does not cause a contradiction. x ~> x', x' ~> x 에 대한 경로가 두 개 존재할 경우 즉, x에서 x'으로 가거나 x'에서 x으로 여러번 걸쳐 지..

Modular factorial Input: Two n-digit integers x and y Output: x! mod y 언뜻 보기에 modular exponentiation과 같다. 이 문제는 P에 속하는 문제일까? Claim : factorization ≤ modular factorial (in the sense that we can solve factorization by calling a subroutine for modular factorial a polynomial number of times.) factorization는 modular factorial로 인해 감축될 수 있다고 한다. gcd(x!, y) = 1 라는 fact를 이용하여 P에 속함을 증명해보도록 하자. (x < d, d는..

Duality Consider a directed graph G where each edge e has a nonnegative integer capacity c(e). Goal is to arrange a flow from a source s to a destination t. Flow consists of assigning an integer f(e) to each edge such that 0 ≤ f(e) ≤ c(e). Goal is to maximize the total flow out of s and into t, called the value of the flow. 양의 정수를 갖는 간선 e의 capacity c(e)에 대해서 방향 그래프 G가 있다. source "s"부터 destinatio..