2-sat, Balancing Numbers

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으로 여러번 걸쳐

지나가거나 한번 걸쳐 지나갈 때 이러한 경로가 2-sat formula φ를 만족시키지 못한다.

이러한 경로가 없다고 가정하고 모순이 생기는지 안생기는지를 먼저 관찰해보도록 한다.

 

Now set the value of some variable.

Ex : letting x to "true" converts any clause of the form (x' ∨ y) into a one-variable clause y

which demands that y be "true".

Let's call these one-variable clauses unit clauses.

 

x' ∨ y 라는 clause 에서 x = "true" 라고 한다면, x' = "false" 이므로 y는 무조건 "true"를 요구한다.

즉, x' ∨ y => y 으로 하나의 변수를 갖는 clause로 변환할 수 있으며 이를 unit clause 라고 한다.

 

Satisfying a unit clause might turn some 2-sat clauses into additional unit clauses, and so on.

This process is called unit clause propagation, and can lead to two possible outcomes

=> cascaed of unit clauses runs out or forced to a contradiction.

 

Suppose we start the unit clause propagation process by setting x to "true" as x ~> x'

does not exist by assumption.

Contradiction at this point occurs if and only if there are paths x ~> y and x ~> y' for some y.

 

즉, 여러 항들중 몇 항들이 unit clause로 변경되는 것을 unit cluase propagation 이라고 한다.

그러나 이를 통해 contradiction 을 얻어낼 수 있다.

x ~> x' 과 같은 unit clause 가 없다는 가정하에서 x = "true" 라고 세팅해보자.

그렇다면 x ~> y, x ~> y'  와 같은 두 경로가 존재할 때, y 가 어떤 boolean이 와도 상관 없게 되는 경우가

발생하게 되므로, contradiction 을 낳을 수 있다. (x ~> y, x ~> y' 둘 중에 한 경로만 있었다면 상관 x)

 

But G(φ) has the following symmetry

=> for any literals l1, l2, there is a path l1 ~> l2 if and only if there is a path l2' ~> l1'.

Thus, if there are paths x ~> y and x ~> y' then there are also paths y ~> x' and

y' ~> x', and hence a path x ~> x'.

So contradiction occurs if and only if there is a path x ~> x' which cannot exist by assumption.

Unit clause propagation continues.

Similar argument if we set x to "false".

 

굉장히 중요한 스킬이 나온것 같다.

G(φ)'s symmetry :  l1 ~> l2 는 l2' ~> l1' 이 존재할 경우에 해당 경로가 존재하는 특성을 이용한 것이다.

그래서 위에서 x ~> y, x ~> y' 와 같은 unit clause 는 y' ~> x', y ~> x 의 경로가 존재할 경우에 존재하며

이는 결국 x ~> y' ~> x' 임으로 x ~> x' 와 같은 경로를 얻게 된다.

 

즉, x ~> y, x ~> y' 두 경로가 존재할 경우 contradiction 을 낳는데 symmetry를 이용하여

x ~> x' 와 같은 경로를 만들어 지므로 이러한 경로가 존재한다면 contradiction 임이 완벽하게 증명되었다.

 

 

Polynomial-time algorithm for 2 - sat

 

while there is an unset variable do
    choose an unset variable x;
    if there is a path x ~> x', then set x = "false";
    else if there is a path x' ~> x, then set x = "true";
    else set x to any value you like;
    while there is a unit clause do unit clause propagation;
end

 

 

reachability

 

Input: A possibly directed graph G and two vertices s and t

Output: Is there a path from s to t?

 

So, we can solve 2-sat by solving 2n instances of reachability,

checking to see if there are paths x ~> x' and x' ~> x for each variable x.

 

2-sat ≤ reachability.

 

So 2-sat is in P.

How about 3-sat? It turns out

 

sat ≤ 3-sat,   k-sat ≤ 3-sat (for any K)

 

In other words, any k-sat formula φ can be converted to a 3-sat formula φ'

which is satisfiable if and only if φ is.

 

 

To prove this, we will show how to convert a sat clause c to a collection of 3-sat clauses

which are satisfiable if and only if c is.

For k = 1, 2,

 

( x ) ⇔ ( x ∨ z 1 ∨ z 2 ) ∧ ( x ∨ z 1 ∨ z 2' ) ∧ ( x ∨ z 1' ∨ z 2 ) ∧ ( x ∨ z 1' ∨ z 2' )

( x ∨ y ) ⇔ ( x ∨ y ∨ z ) ∧ ( x ∨ y ∨ z' )

 

k = 1 일 경우 z1, z2에 대한 dummy node를 추가하였고,

k = 2 일 경우에 z에 대한 dummy node를 추가하여 3-sat 으로 구성하였음을 알 수 있다.

 

For  k > 3, a k-sat clause becomes k - 2 3-sat clauses linked together by k - 3 dummy variables zi.

ex : for k = 5,

 

( x 1 ∨ x 2 ∨ x 3 ∨ x 4 ∨ x 5 ) ⇔ ( x 1 ∨ x 2 ∨ z 1 ) ∧( z 1' ∨ x 3 ∨ z 2 ) ∧( z 2' ∨ x 4 ∨ x 5 )

 

If there was a way to break these clauses down even further so that they have just two literals each,

we would have 3-sat ≤ 2-sat.

No simple way to achieve this, however.

 

k = 4, 5, ... 에 대해서 k-sat의 각 clause를 k - 2 개의 3-sat clause들로 연결시킬 수 있으며 k - 3 개의 dummy

node를 추가함으로써 3-sat 으로 구성이 가능하다.

그러나 이렇게 만들 수 있는 과정이 쉽지는 않다는 점을 알아두자.

 

---

Balancing Numbers

 

integer partitioning

Input: A list S = {x1, ..., xl} of positive integers 

Question: Is there a balanced partition, a subset A ⊆ {1, ..., l} such that

subset sum

Input: A set S = {x1, ..., xl} of positive integers and an integer t

Question: Does there exist a subset A ⊆ {1, ..., l} such that

Clearly, integer partitioning ≤ subset sum.

Claim: subset sum ≤ integer partitioning.

 

사실 subset sum에 대한 문제는 알고리즘 수업시간에 했던 것 처럼 NP 문제이다.

그 말은 즉, integer partitioning 또한 NP에 속하는 문제인데 이를 확인해보도록 하자.

 

Suppose we have an instance of subset sum with total weight W = (x1 + ... + xi) and

target weight t.

Add an additional integer y so that we can put half of W + y on each side if and

only if there is a subset A with total weight t.

 

W = (w1 + ... + wi), 그리고 목표 가중치 t를 설정하였을 때,

t의 부분 집합 A가 있는 경우에만 W + y의 절반을 양쪽에 놓을 수 있도록 양수 y를 더한다.

그리고 t를 어떻게 잡느냐에 따라 다음과 같이 case를 나눌 수 있다.

 

Suffices to consider the following three cases:

① If t = W/2, we are done. (y = 0)

② If t < W/2, set y = W - 2t. Then t + y = (W + y)/2,

      so one side consists of A ∪ {y} and the other of A¯.

 

 

③ If t > W/2, set y = 2t - W. Then t = (W + y)/2,

      so one side consists of A and the other of A¯  ∪ {y}