Exact One

問題概要

$N$ 個の二値変数 $x_1, \cdots, x_N \; (x_i \in \{ 0, 1 \})$ がある。

『いかなる場合でも $x_1, \cdots, x_N$ のうち1つだけ $1$ をとり、それ以外は $0$ をとる。』 これを $\wedge, \; \vee, \; \neg$ を用いて表現せよ。

一般に、この問題を満たす状態を $Exact \; One(EO)$ と呼ぶ。

---

条件なしなら

$x_1, \cdots, x_N$ の総和が $1$ になればいいので、以下で表せる

$$\sum\limits_{i=1}^{N} \; x_{i} \; = \; 1$$

---

問題を分解する

『 $x_1, \cdots, x_N$ のうち、どれか1つのみが必ず $1$ 』と言うのは以下のように分解できる

• $x_1, \cdots, x_N$ のうち、少なくとも1つは $1$ である $\cdots$ $At \; Least \; One(ALO)$
• $x_1, \cdots, x_N$ のうち、多くとも1つは $1$ である $\cdots$ $At \; Most \; One(AMO)$

この $ALO$ と $AMO$ をどちらも満たす場合、問題と等価である。

---

論理式の形にする

ALO

少なくとも1つが $1$ の時に、真になれば良いので、

$$\bigvee_{i=1}^{N} \; x_i$$

上の式が真になれば良い。

AMO

多くとも1つが $1$ の時に、真になれば良い。 しかし、$ALO$ とは違い、ひと工夫が必要で 『同時に2つ以上が $1$ にならないことを保証すればいい』、すなわち、 『任意の二つの変数 $x_i, \; x_j$ が同時に $1$ とならない』 を全ての組み合わせで満たせば良い。

すなわち、下の式が真になれば良い。

$$\bigwedge_{i=1}^{N-1} \; \bigwedge_{j=i+1}^{N} \; \neg \;(x_{i} \wedge x_{j})$$

このような実装は pairwise encoding と呼ばれる。

---

最後

Exact One は ALO, AMO が同時に満たされている状態なので、

$$\left( \bigvee_{i=1}^{N} \; x_i \right) \; \wedge \; \left( \bigwedge_{i=1}^{N-1} \; \bigwedge_{j=i+1}^{N} \; \neg \;(x_{i} \wedge x_{j}) \right)$$

が真になるとき、$x_1,\dots,x_N$ のうち、ちょうど1つのみが $1$ であることを表す論理式となる。

---

おまけ(制約数について)

この手法における制約数について考える。

• ALO: 1つの論理式で、長さが $N$ なので、$O(N)$
• AMO: 任意の2つの変数の取り方が $\tbinom{N}{2}$ なので、$O(N^2)$

となるので、制約数は $O(N^2)$ となる。