Satisfiability Problem

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는 y의 divisor)

 

 

Proof:

If we can find the smallest divisor d of y, which is necessarily a prime,

we can divide y by d and recurse until we have factored y completly.

Since d ≥ 2, this will take at most log2(y) = O(n) steps.

 

y를 나눌 수 있는 가장 작은 d는 반드시 소수다.

   (1) Prime : 2, 3, 5, 7, ... 를 고려하면 반드시 d = 2, 3, 5, 7, ... 즉, 소수이며

   (2) Composite : 4,10, 25, ... 를 고려하면 d = 2, 2, 5, ... 이 또한 소수이다.

d값은 무조건 2 이상이므로 log2(y) = O(n) 임은 당연하다.

 

To find the divisor d, we use the fact that

   (1) gcd(x!, y) = 1 (x < d)

   (2) gcd(x!, y) = gcd(x! mod y, y)

 

Since we can find the gcd of two n-digit numbers in polynomial time,

we can tell whether x < d with one call to modular factorial.

 

One call to modular factorial tells us whether x < d or not.

Starting with x = y^(1/2)/2, we can locate d using binary search on the interval

ranging from 2 to y which takes O(log(y)) = O(n) steps.

 

Therefore, we can find d with O(n) calls to modular factorial.

We factor y completely by finding such d at most O(n) times.

 

 

예시를 들어보도록 하자.

Factorize y = 1,000,000.

만약 y가 factor를 갖는다면 그 값은 적어도 1000 보다는 작거나 같아야 한다. 

이 때, x = (2 + 1000) / 2 = 501을 뽑는다. (binary search 기법 활용, 2 ~ 1000)

 

(1) gcd(501!, 1,000,000) = 1 일 경우 501은 y의 divisor 보다 작은 경우다.

      따라서 이 경우에 x = (502 + 1000) / 2 를 뽑는다. (502 ~ 1000)

(2) gcd(501!, 1,000,000) != 1 일 경우 501은 y의 divisor보다 크거나 같은 경우다.

      따라서 이 경우에 x = (2 + 501) / 2 를 뽑는다. (2 ~ 501)

 

따라서, O(log y^(1/2)) = O(n) time 만에 x를 선택할 수 있다.

y를 y/d 로 update하고 과정을 반복하면 된다.

 

 

---

 

Needles in a Haystack: the Class NP

 

 

Hamiltonian path

Input: a graph G

Question: does there exist a Hamiltonian path on G?

 

yes-or-no로 대답할 수 있는 결정 문제이다.

이 문제에 대해서 polynomial time algorithm으로 해결하지 못한다는 것을 알고 있다.

그러나, "yes" 라고 대답할 수 있다면?

   => There is an easily checkable proof of that fact, namely, the Hamiltonian path itself.

 

NP is the class of decision problems with this kind of logical structure where yes-instances

are easy to verify.

A decision problem is in NP if, whenever the answer for a particular instance is "yes",

there is a simple proof of this fact.

 

특정 문제에 대한 결정을 내릴 수 있을 경우("yes"), 해당 문제는 NP에 속하는데 이에 대한 증명을 알아보도록 하자.

 

 

By "simple proof", we mean a proof that we can check in polynomial time.

(ex : 주어진 경로가 linear time으로 Hamiltonian 임을 확인하는 것을 의미)

NP is a asymmetric notion!

If i happen to know the path, it's easy to prove to you that the graph is Hamiltonian.

On the other hand, there no easy way to prove that a non-Hamiltonian graph has no such path.

 

즉, 해당 경로를 인지하고 있다면 해밀턴 경로임을 증명하는 것은 쉽지만

해밀턴 그래프가 아닌 경우에 해밀턴 경로를 갖지 않는다는 것을 증명하는 것은 쉽지가 않다!

 

If the input is a yes-instance, the sequence of steps executed by the algorithm constitutes

a proof of this fact.

P ⊆ NP

 

Essentially, P is the subset of NP consisting of problems for which there is some mathematical

insight that lets us avoid an exhaustive search.

The question of whether or not P ≠ NP is considered one of the most profound questions

in computer science.

 

예를 들어서 해밀턴 경로가 polynomial time algorithm이 없다는 것을 모든 사람들이 알고있는 사실이다.

그러나? => P에 속한다는 것을 그 누구도 증명하지 못한다는 점이다.

즉, 누구도 P에 속한다는 것을 찾지 못하기 때문에 이도저도 못한 상황이 되버린 것이다.

 

 

Coloring Graphs

 

Suppose each conference participant supplies the organizers with the list of talks they want to hear.

Assume enough supply of lecture rooms however only k time slots.

Can we assign a time slot to each talk so that no two talks take place simultaneously if someone wants to see the both?

 

참여자들이 서로 겹치지 않고 강연을 들을 수 있도록 스케줄링하도록 하는 문제이다.

 

Let G = (V, E)

V = {talks} and E = {someone wants to see both talks}.

We want to assign one of the k time slots (or colors) to each vertex such that

adjacent vertices have different time slots.

 

 

A k-coloring is an assignment of one of k different colors to each vertex, 

and a coloring is proper is no two adjacent vertices have the same color.

 

좀 더 이해할 수 있도록 예시를 들어보도록 하자.

"A", "B", "C" 라는 강연이 있으며 "x", "y", "z" 라는 사람이 있다고 하자.

 

(1) "x"는 강연 "A", "B", "C" 를 전부 듣고 싶어한다.

(2) "y"는 강연 "A" 만 듣고 싶어한다.

(3) "z"는 강연 "A", "C" 를 듣고 싶어한다.

 

즉, V = { "A", "B", "C" } 가 있으며 Graph를 그려보면 다음과 같다.

 

(1) "x"는 "A" 에 있으면 "A" => "B" => "C" or "A" => "C" => "B" 으로 이동하면서 강연을 들을 수 있거나

                  "B" 에 있으면 "B" => "A" => "C" or "B" => "C" => "A" 으로 이동하면서 강연을 들을 수 있거나

                  "C" 에 있으면 "C" => "A" => "B" or "C" => "B" => "A" 으로 이동하면서 강연을 들을 수 있다.

(2) "y"는 "A" 에서 강연을 들을 수 있다.

(3) "z"는 "A"에 있으면 "A" => "C" 으로 이동하면서 강연을 들을 수 있거나

                  "C"에 있으면 "C" => "A" 으로 이동하면서 강연을 들을 수 있다.

 

즉, 이런 식으로 vertex에 색을 칠함으로써 사람들이 강연을 들을 수 있도록 해야 한다.

 

 

graph k-coloring

 

Input: A graph G

Output: Is there a proper k-coloring of G?

 

graph k-coloring is in NP since it is easy to check that a coloring is proper.

However, this does not tell us how to find a proper coloring in k^n possible colorings.

 

Cleary, graph 1-coloring is in P.

Claim : graph 2-coloring is in P.

 

 

Satisfiability Problem

 

Consider the following CNF (conjunctive normal form)

φ (p, q, r) = ( p ∨ q' ) ∧ (p' ∨ r' ) ∧ ( q ∨ r ) ∧ ( p ∨ q ).

If φ (p, q, r) = "true" for a particular assignment of truth values to the variables,

we say that this assignment satisfies φ.

 

sat

Input: A CNF Boolean formula φ(x1, ..., xn).

Question: Is φ satisfiable?

 

Easy to check whether a given truth assignment is satisfying.

So sat ∈ NP.

graph coloring and sat both are constraint satisfaction problems. 

 

Claim: sat for such formulas is in P.

 

A CNF formula can be converted into a DNF formula using the distributive law:

 

 (  x 1 ∨ y 1 ) ∧ ( x 2 ∨ y 2) = ( x 1 ∧ x 2 ) ∨ ( x 1 ∧ y 2 ) ∨ ( y 1 ∧ x 2 ) ∨ ( y 1 ∧ y 2 )

 

디지털 회로개론 시간에 배웠던 걸 응용해보면...

(x1 + y1)(x2 + y2) = x1x2 + x1y2 + x2y1 + y1y2 으로 2개의 term이 4개의 term으로 늘어난 것을 알 수 있다.

 

A CNF formula with m clauses and k variable per clause is converted into a DNF formula

with k^m clauses each with m variables. (위에서 확인)

Therefore, converting CNF formulas to DNF ones can increase their size exponentially,

and this conversion does not qualify as a polynomial-time reduction.

 

 

k-sat

Input: A CNF Boolean formula φ where each clause contains k variables.

Question: Is φ satisfiable?

 

Clearly, 1-sat is in P.

 

1-sat이 P인 이유는?

φ(xi) = x1' ∧ x2 ∧ x3' ∧ x4 ∧ ... ∧ xn 라는 boolean formula φ가 있다고 가정하자.

이때, x1, ..., xn에 대한 Truth table을 만드는데 O(2*n) 만큼 걸리기 때문에 모든 boolean이

true가 되도록 하는 x1, ..., xn을 찾는데 결국 O(n), polynomial time 이 걸린다.

 

Claim: 2-sat is in P. Note first,

 

(l1 ∨ l2 ) ⇔ ( l1' → l2) and ( l2' → l1 )

 

For a 2-sat formula φ with n variables, x1, ..., xn, define a graph G(φ) with 2n vertices

representing the 2n possible literals xi and (xi)' and with a pair of directed edges between

these vertices for each clause.

This can be done in polynomial time.

The figure shows G(φ) for φ (p, q, r) = ( p ∨ q' ) ∧ ( p' ∨ r' ) ∧ ( q ∨ r ) ∧ ( p ∨ q)

 

 

(1) variable이 3개이므로 6개의 vertex가 존재하며

(2) 각 clause마다 directed edge의 쌍을 보유하므로 clause가 4개여서 총 8개 존재한다.

 

Let x ~> y to mean that there is a path, i.e., a chain of implications, from the literal x to the literal y.

 

예를 들어서 φ(l1, l2, l3) = (l1 ∨ l2 ) ∧ ( l2' ∨ l3 ) ∧ (l1 ∨ l3') 에 대한 formula를 보도록 하자.

이러한 formula는 다음과 같다. (위에서 정의된 스킬을 이용)

 

((l1' → l2), (l2' → l1)) ∧ ((l2 → l3), (l3' → l2')) ∧ ((l1' → l3'),(l3 → l1))

 

l1' ~> l1 => Set l1 to "true"

l1' → l2 → l3 → l1 이므로 즉, l1' ~> l1 인 경우에 l1' ~> l1 는 항상 "true" 여야 한다.

왜냐하면 l1' ~> l1는 l1 ∨ l2 ∨ l3 ∨ l1 인데 적어도 l1은 "true" 여야 한다.

l1' = F, l1 = T 라고 할 때, 위 formula를 다음과 같이 변경할 수 있다. 

 

((F → l2), (l2' → T)) ∧ ((l2 → l3), (l3' → l2')) ∧ ((F → l3'),(l3 → T))

 

Set l2 to any, say "false". Then l3 can be set to any.

If we set l2 to "true", then we need to set le to "true".

 

l2 → l3 에 대한 식은 l2' ∨ l3 으로 변경할 수 있다.

case 1 : l2가 "false" 이면 l2'는 "true" 이므로 l3는 뭐가 와도 상관이 없다.

case 2 : l2가 "true" 이면 l2'는 "false" 이므로 l3는 항상 "true" 가 와야 한다.