ZOE (Zero One Equation)

$\left[\begin{matrix} 1 & 0 \\ 0 & 1 \\1&0\end{matrix}\right] \times \left[\begin{matrix} x_1\\x_2\end{matrix}\right] = \left[\begin{matrix} 1 \\ 1 \\1\end{matrix}\right]$ A x 1

3D Matching → ZOE

• 3D matching: m (boys, girls, pets), n triples
• create 0-1 var $x_1 , … , x_n$ for each triple $x_i=1$ means chosen.
• for each boy,girl,pet, triple containing them are $j_1, …, j_k$ then $x_{j_1} + … + x_{j_k}= 1$ ↔ perfect matching

Therefore 3D matching problem reduced into ZOE problem

ZOE is NP-Complete

ZOE → Subset Sum

Given a set of integers, target W find subset of integers that sum = W

• Given an Instance A of ZOE construct like this
  • 행렬의 열벡터를 진수로 생각할 수 있다
    • 여기서 2진수는 carry때문에 오류 발생 가능 따라서 n+1 진수로 생각하면 해결!
  • W=111..111로 생각할 수 있다
  • 따라서 숫자들중 몇개를 뽑아서 합이 W가 되는 문제와 동치!
• 재미있는 사실 Subset sum은 사실 knapsack의 특수한 경우로, n과 W에 poly하게 풀린다 O(nW) → P아닌가요??
  • 그러나! P-Class에 속하려면, n과 W의 input size에 대해 poly여야 한다
  • W는 숫자이므로, representation(ex. 10진수)에는 log W가 필요하다 즉 input size는 log W인 것이다
  • P-Class : poly(n, logW) 그러나 knapsack : poly of (n, W) ↔ exp(log W) ↔ exp(input size)
  • 따라서 P-Class라고 오해할 수 있으나 아니고 NP이다.

Therefore ZOE reduced into Subset Sum Problem

Subset Sum is NP-Complete

ZOE → ILP

ILP: Integer Linear Programming