Designing Reduction

circuit  sat

Input: A Boolean circuit C 

Question: Is C satisfiable?

Note  that  a  Boolean  circuit  is  a  powerful  enough  model  of computation  to  express  any  algorithm.
We  will  show  witness  existence  ≤  circuit  sat  implying  circuit  sat  is NP-complete.

We  will  convert  an  instance  of  (Π, x, t)  of  witness  existence  to  a Boolean  circuit  C   of  

polynomial  size  s.t.   C   is  satisfiable  if  and  only if  there  is  a  witness  w  for  which  Π(x, w)  

returns  “yes”  within  t steps.

 

Boolean 회로는 어떠한 알고리즘을 표현할 수 있는 계산적 모델을 나타낼 만큼 강력하다.

witness existence를 circuit sat으로 감축하는 것이 circuit sat이 NP-complete 임을 암시하는 것을 보일 것이다.

먼저 witness existence에 대한 (Π, x, t) 의 인스턴스를 polynomial size의 Boolean 회로로 변환한다.

이 때, C는 t 단계 이내에 Π(x, w) 가 "yes"를 반환하는 증인 w가 존재할 경우에만 satisfiable 한다. 

 

The  reduction  is  made  by  “compiling”  the  program  Π(x, w)  into  C . 

In  fact,  any  program  is  compiled  into  sequences  of  instructions  in machine  language  

that  are  executed  on  a  chip  made  of  logical  gates. 

A  single  step  of  Π  corresponds  to  a  layer  of  C   and  if  Π  contains “for”  or  “while”  loops,  

can  build  C   by  “unrolling”  these  loops  and repeating  the  corresponding  layers  in  C .

Since  Π’s  running  time  is  at  most  t  steps,  C   has  O(t)  layers.

Π has access to at most O(t) different locations in memory, so the number of bits that 

needs to be carried from a layer to the next in C is O(t). ⇒ C ’s size is O(t^2).

This  gives  a  circuit  whose  inputs  correspond  to  the  bits  of  x  and  w, and  whose  output  is  

“true”  if  and  only  if  w  is  a  witness  for  x.

 

감축은 프로그램  Π(x, w)를 C로 "컴파일" 함으로써 만들어진다.
만약 Π가 "for" 또는 "while" 루프를 포함하면 Π의 단일 단계는 C의 레이어에 해당하며,

이러한 루프를 "unrolling" 하고 C에서 해당 레이어를 반복하여 C를 만들 수 있다.

Π의 실행 시간은 대부분의 t 단계이기 때문에, C는 O(t) 레이어를 가지고 있다.

Π는 메모리의 대부분의 O(t)에 대한 다른 위치로 접근할 수 있으므로, C 내에서 레이어에서 다음 레이어로

이동해야 하는 비트의 수는 O(t) 이다. 

즉, C의 크기는 O(t^2) 이다.

 

이것은 입력이 x와 w의 비트에 해당하는 회로를 제공하고, w가 x의 증인인 경우에만 출력이 "참"인 회로를 제공한다.

 

 

We  will  now  show  3-sat  is  NP-complete  from  the  reduction.

circuit  sat  ≤  3-sat.

 

Unless  P  =  NP,  a  large  jump  in  k-sat’s  complexity  is  observed  when k  goes  from  2  to  3.
Need  to  show  the  3-sat  formula  φ  is  satisfiable  if  and  only  if  a Boolean  circuit  C   is.
The  relationship  y  =  x1 ∧ x2 can  be  written  in  sat  form  as

(x1 ∨ y¯) ∧ (x2 ∨ y¯) ∧ ( x1¯ ∨ x2¯ ∨ y).

 

윗 식이 과연 항상 true인지를 확인해보자.

x1 = true, x2 = true, y = true     : (true) ∧ (true) ∧ (true) = true

x1 = true, x2 = false, y = false  : (true) ∧ (true) ∧ (true) = true

x1 = false, x2 = false, y = false : (true) ∧ (true) ∧ (true) = true

 

직접 대입해본 결과 y = x1 ∧ x2 와 동치임을 알 수 있다.

 

Similarly,

y  =  x1 ∨ x2    ⇔    ( x1¯ ∨ y) ∧ ( x2¯ ∨ y) ∧ (x1 ∨ x2 ∨ y¯)

y  =  x¯    ⇔    (x ∨ y) ∧ ( x¯ ∨ y¯)

 

and  the  output  being  “true”  is  a  one-variable  clause.

 

 

위에 Boolean circuit 에 대한 y1, y2, y3, z 에 대한 관계식을 먼저 작성해보도록 한다.

y1 = x1 ∧ x2,   y2 = x1 ∨ x2,   y3 = y1¯ ,   z = y2 ∧ y3   

그렇다면 z가 항상 true 이기 위에서 아래와 같은 식이 도출된다.

 

The  Boolean  circuit  in  Fig.   5.2  becomes  the  following  formula.

φ  =  (x1 ∨ y¯1) ∧ (x2 ∨ y¯1) ∧ ( ¯x1 ∨ x¯2 ∨ y1)

                 ∧  ( ¯x1 ∨ y2) ∧ ( ¯x2 ∨ y2) ∧ (x1 ∨ x2 ∨ y¯2)

∧  (y1 ∨ y3) ∧ ( ¯y1 ∨ y¯3)                      
           ∧  (y2 ∨ z¯) ∧ (y3 ∨ z¯) ∧ ( ¯y2 ∨ y¯3 ∨ z) 

∧  z.  (마지막에 intersection z 필수)          

Any  circuit  C   with  n  gates  is  converted  to  a  sat  formula  φ  with O(n)  clauses  that  

is  satisfiable  if  and  only  if  C   is.

3-sat  is  one  of  the  most  basic  NP-complete  problems  that  can  be used  to  show  

NP-completeness  of  other  problems.

 

 

Designing Reductions

 

circuit  sat  is  NP-complete  because  Boolean  circuits  are  powerful enough to  carry  out  

any  computation.
3-sat is NP-complete because it is powerful enough to express the claim that a Boolean 

circuit works and that its output is “true.”

 

Boolean circuit이 어떠한 computation을 실행할 수 있다는 점에서 강력하다는 이유로 circuit sat을

NP-complete 라고 한다.

따라서 Boolean circuit 을 통해 output 이 "true"임을 명백하게 표현할 수 있다는 점에서 3-sat을

NP-Complete 라고 한다.

We  will  now  show  other  problems  that  are  NP-complete. 

sat  has  many  variants  in  which  various  kinds  of  contraints  are satisfied.
In  naesat  (not-all-equal  sat),  literal  assignments  of  all  equal  value  in any  clause 

(l1, · · · , lm)  are  not  allowed.
Unlike  sat,  naesat  is  symmetric  wrt  switching  the  Boolean  values “true”  and  “false.”  

(useful  in  proving  other  NP-complete  problems with  similar  symmetry.)

 

임의의 절 (l1, · · · , lm)에서 모든 동일한 값의 문자 할당은 허용되지 않는다.
sat과 달리 naesat는 boolean 값을 "true"과 "false"으로 전환하는 symmetric wrt이다.

 

We  can  define  nae-k-sat  where  there  are  k  literals  in  each  clause. 

Claim:   nae-2-sat  ≤  graph  2-coloring.   So,  nae-2-sat  is  in  P.

We  now  show  that

3-sat  ≤  nae-3-sat.

So,  just  like  k-sat,  nae-k-sat  goes  from  easy  to  hard  when  k  goes from  2  to  3.

Note  first  that

(x, y, z)  =  (x ∨ y  ∨ z) ∧ ( x¯ ∨ y¯ ∨ z¯).

Note  furthermore  that  if  a  truth  assignment  satisfies  a  naeset formula, 

then  so  does  its  complement.

 

위 식에서 만약에 x, y, z가 동일할 경우(전부 true or 전부 false),

(true) ∧ (false) = false 즉, false가 되므로 naesat 을 만족하지 않는다.

 

To  build  on  this  observation,  we  can  convert  a  3-sat  formula

φ  =  (x1 ∨ y1 ∨ z1) ∧ · · · ∧ (xm ∨ ym ∨ zm)

by  introducing  a  dummy  variable  s  into  the  following  nae-4-sat formula

φ ′ =  (x1, y1, z1, s) ∧ · · · ∧ (xm, ym, zm, s).

This is a valid reduction since φ is satisfiable if and only if φ′ is. 

 

(⇒) ∃ a truth assignment s.t. every clause has at least one true literal.   

Setting  s  =  “false”  satisfies  φ′.

(⇐)  since  satisfying  assignments  for  naesat  formula  come  in complementary  pairs,  

φ′ must  have  a  satisfying  assignment  where s  =  “false.”   

In  this  case,  at  least  one  of  the  other  literals  in  each clause  must  be  true.

 

적어도 하나의 문자가 "true" 여야 하므로 s = "false" 라고 설정하고 이에 대해서 satisfiable 해야 한다.

즉, nae-4-sat formula 에서

(1) xi, yi, zi 가 전부 true 이거나 false 일 경우 : (xi, yi, zi, s) = false.

(2) xi, yi, zi 가 전부 true 이거나 false가 아닌 경우 : (xi, yi, zi, s) = true.

 

따라서 xi, yi, zi 중에 적어도 하나의 "true" 를 포함하게 되므로 항상 "true" 가 나옴을 알 수 있다.

φ ′ 가 satisfiable 하다면 결국 φ 는 xi, yi, zi 중에 적어도 하나의 "true" 를 반드시 포함하므로 이 또한

satisfiable 한 것을 알 수 있다.

 

So,  3-sat  ≤  nae-4-sat.

Claim:   Using  the  same  argument  that  transformed  4-sat  into  3-sat, 

we  can  show  nae-4-sat  ≤  nae-3-sat.

I.e.,  since

(w, x, y, z)  ⇔  (w, x, s) ∧ (y, z, s¯),

a  nae-4-sat  formula  is  satisfiable  if  and  only  if  a  nae-3-sat  formula  is

 

3-sat  ≤  nae-4-sat  ≤  nae-3-sat.

 

 

Example

Find  a  direct  reduction  from  circuit  sat  to  nae-3-sat. 

 

First  consider  clauses  corresponding  to  an  and:

y  =  x1 ∧ x2 ⇔  (x1 ∨ y¯) ∧ (x2 ∨ y¯) ∧ (x1¯ ∨ x2¯ ∨ y).

 

위 식이 맞는지 부터 확인해보자.

(1) x1 = true, x2 = false, y = false : (true) ∧ (true) ∧ (true) = true 

(2) x1 = x2 = y = false : (true) ∧ (true) ∧ (true) = true

(3) x1 = x2 = y = true : (true) ∧ (true) ∧ (true) = true

 

성립하는 것을 확인하였다.

As in the reduction from 3-sat to nae-3-sat, we can introduce a global dummy variable w, and 

focus on satisfying assignments where w is false.
Then  consider  the  nae-3-sat  clauses

(x1, y¯ , w) ∧ (x2, y¯ , w) ∧ (x1¯ , x2¯ , y).

 

일단 예측할 수 있는 것은 (x1¯, x2¯, y) = true 임을 앞에서 확인하였다.

그렇다면 (x1, y¯, w), (x2, y¯, w) 에 대해서 항상 true 일까?

일단 w를 "false" 임을 고려할 때, x1 = "false" 일 경우 y는 항상 "false" 이므로 y¯ 는 "true" 이기 때문에 맞다.

그렇다면 x1, x2 둘 다 "true" 일 경우에는 w가 "false" 이기 때문에 이 또한 맞다.

따라서 위 식이 satisfiable 함을 알 수 있겠다.

 

The  first  two  clauses  ensure  that  if  either  x1 or  x2 is  false  (the value  of  w),  then  y  must  be  false.   The  third  clause  then  forces  y  to be  true  if  x1 and  x2 are  both  true.

 

Now  consider  clauses  corresponding  to  an  or:

y  =  x1 ∨ x2 ⇔  (x1¯ ∨ y) ∧ (x2¯ ∨ y) ∧ (x1 ∨ x2 ∨ y¯). 

 

Then  consider  the  nae-3-sat  clauses

(x1¯, y, w) ∧ (x2¯, y, w) ∧ (x1, x2, y¯).

 

Similar  argument  as  before  applies.

For  a  not  gate,  if  y  =  ¯x,  then  include  the  clauses  (x, y, w) ∧ (x, y, w¯). 

 

⇒  Each  gate  is  replaced  with  a  constant  number  of  clauses,  and  therefore  we  make  

this  reduction  in  polynomial  time  as  it  produces a  formula  of  polynomial  size.

 

 

Let’s  now  reduce  3-sat  to  graph  3-coloring.
Note  first  that  the  constraints  in  graph  3-coloring  are  inherently symmetric  wrt  

permutation  of  the  colors.
⇒  Easier  to  work  with  constraints  that  are  symmetric  wrt  to “true”  and  “false.”
I.e.,  work  with  naesat  or  nae-3-sat. Refer  to 

 

 

첫번째 사진 :  "true" 일 경우 black, "false" 일 경우 white으로 설정하므로 x = y = "true", z = "false" 임을

알 수 있으며 상단 노드는 central vertex으로 "true", "false" 에 대한 connection 을 돕기 때문에 다른 색이므로

Graph 3-coloring 임을 알 수 있다.

 

두번째 사진 :  사진과 같이 (x, y, z) ∧ (x¯, y, z¯) 에 대한 nae-3-sat을 활성화 시킬 것이다.

그렇다면 (x, y, z)에 대해서 x, y, z와 연결된 정점에 대해서 색이 달라야 하며 (x¯, y, z¯) 에 대해서도 연결된

정점에 대해서 색이 달라야 한다. (3-coloring 임을 위해)

 

세번째 사진 : 결국 세개의 문자의 동일한 "true" 값을 갖지 않는다는 NAE-3-SAT 제약을 강제한다.
표시된 두 개의 제약은 NAE-3-SAT 공식에 해당하는 것이 분명하다.

즉, (x, y, z) 에서 x = y = z = "true" 일 경우 NAE-3-SAT 에 해당하지 않으므로 3-coloring 을 만족하지 않는다.

 

 

So,  we  can  convert  nae-3-sat  formula  φ  with  n  variables  and  m clauses  into  a  graph  G  

with  2n + 3m + 1  vertices,  which  is 3-colorable  if  and  only  if  φ  is  satisfiable.

 

위 사진으로는 총 13 개의 정점이 존재하는데

(x, y, z, 그리고 complement 한 정점들) + (formula 로 만들어진 정점들) + (central node) = 13 이다.

Since  this  conversion  can  be  carried  out  in  polynomial  time  ⇒

nae-3-sat  ≤  graph-3-coloring

Claim:   graph  k-coloring  ≤  graph  k  + 1-coloring  for  any  k.

By  induction,  graph  k-coloring  is  NP-complete  for  any  k  ≥  3.

 

 

Example

constrained  graph  3-coloring
Input:   A  graph  G  with  n  vertices  and  a  list  f1, · · · , fn ∈  {1, 2, 3} 

Question:   Does  G  have  a  proper  3-coloring  c1, · · · , cn  where  cv ≠ fv,    ∀v?

 

그래프 G의 정점 f1, ..., fn 에 대해서 1, 2, 3 중에 하나가 선택이 된다고 한다.

이 때 적절하게 c1, ..., cn 을 택하여 cv = fv 가 전부 되지 않도록 하는 그래프가 존재하는지에 대한 문제이다.

We  will  show  constrained  graph  3-coloring  ∈  P  by  reducing  it  to 2-sat.
For  each  vertex  v,  define  Boolean  variables  rv, gv, bv where  rv is true  if  v  is  colored  red  

and  false  otherwise,  and  so  on.

Constraints  between  neighboring  vertices  u, v  can  be  expressed  as 2-sat  clauses  which  force  

them  to  be  different  colors:

(ru¯ ∨ rv¯) ∧ (gu¯ ∨ gv¯) ∧ (bu¯ ∨ bv¯).

 

graph 3-coloring 을 감축함으로써 2-sat 을 만든 것을 볼 수 있다.

위 공식에 대해서 정점 u, v에 대해서 색깔이 동일할 경우에 (false ∨ false) = false 이므로

이 경우는 만족하지 않는다.

따라서 2-sat을 감축함으로써 P에 속하는 graph 3-coloring 을 만들 수 있음을 확인할 수 있다.

 

Similarly,  we  can  write  the  restriction  that  each  vertex  has  a  single color,  but  not  its  

forbidden  one,  as  a  2-sat  clause.
E.g.,  if  v  cannot  be  red,  write  (gv ∨ bv)  forcing  at  least  one  of  gv and  bv to  be  true.
This  is  clearly  a  polynomial-time  reduction.
We  note  that  we  can  ensure  exactly  one  of  gv and  bv is  true  by  also including 

the  clause  (gv¯ ∨ bv¯),  but  this  isn’t  necessary.

 

각 정점은 반드시 하나의 색깔을 가지고 있어야 하며 2-sat을 이용하여 만들 수 있다.

정점 v가 빨강색이 아닐 경우 초록색, 파랑색 둘 중 하나가 반드시 되어야 하는데 이를 polynomial time으로 감축할 수 있으며  (gv¯ ∨ bv¯) 에 대한 항을 포함하여 true 임을알아낼 수 있는데 반드시 필요한 건 아니다. (위에 주어진 항만으로 충분)

Note  furthermore  that  we  can  reduce  graph  (k  − 1)-coloring  to constrained  graph  

k-coloring  by  forbidding  the  same  color  at  every vertex.
Since  graph  k-coloring  is  NP-complete  for  k  ≥  3,  constrained  graph k-coloring  is  

NP-complete  for  k  ≥  4.

 

즉, 위에서 본 것처럼 제한된 3-coloring 이 2-sat 을 감축시킴으로써 만든 것 처럼

모든 정점이 동일한 색을 금지하는 제한된 k-coloring 을 (k - 1)-sat 즉, (k - 1)-coloring 을

감축시킴으로써 만들 수 있다.

따라서 constrained graph k-coloring 은  k  ≥  4 일 경우 NP-complete 임을 알 수 있다.