制約充足問題

同義語:constraint satisfaction problem

概要

制約充足問題(constraint satisfaction problem)とは、有限集合の上の関係の有限集合 $\Gamma$ を固定し、$\Gamma$ の関係で書かれた制約の列にすべてを満たす値の割り当てがあるかを問う判定問題 $\mathrm{CSP}(\Gamma)$ で、グラフの彩色や 3SAT を含み、関係構造の間の準同型の存在の問題と同じである。$\Gamma$ の関係をすべて保つ演算(多相写像)が、原始正に定義できる関係を決め、従って計算量を決める。2 元の集合の上では、定数・min・max・多数決・少数決のどれかを多相写像にもてば多項式時間で解け、そうでなければ NP完全である(Schaefer の二分定理)。一般の有限集合でも、弱全会一致演算の有無で同じ二分が成り立つ(Bulatov と Zhuk)。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: NP完全, グラフ準同型

制約充足問題(constraint satisfaction problem)は、有限集合 $D$ の上の関係の有限集合 $\Gamma$ を固定し、「$\Gamma$ の関係で書かれた制約を並べたものが与えられたとき、すべての制約を満たす値の割り当てがあるか」を問う判定問題 $\mathrm{CSP}(\Gamma)$ である。グラフの彩色や 3SAT はこの形に書ける。$\mathrm{CSP}(\Gamma)$ はつねに NP に属し、問題はどの $\Gamma$ で多項式時間で解け、どの $\Gamma$ で NP完全 になるかである。
Feder と Vardi は、どの有限の $\Gamma$ についても $\mathrm{CSP}(\Gamma)$ は多項式時間で解けるか NP完全かのどちらかであると予想した(BKW17 Conjecture 10, p. 5)。2 元の集合の上では Schaefer が 1978 年にこれを示していた(Sch78)。一般の場合は 2017 年に Bulatov(Bul17)と Zhuk(Zhu20)が独立に解決した。分類の鍵は、$\Gamma$ の関係をすべて保つ演算(多相写像)である。
この記事では thm-csp-reduction・thm-csp-galois・thm-csp-semilattice・thm-csp-affine を証明し、主定理として Schaefer の二分定理(thm-csp-schaefer)を、Post の分類から従う補題と多数決の場合だけを引用して証明する。

定義と例

制約言語と制約充足問題

$D$ を空でない有限集合とする。$D$ の上の $n$ 項関係($n\ge1$)とは部分集合 $R\subseteq D^n$ のことである。空でない関係の有限集合 $\Gamma$ を $D$ 上の 制約言語 という。
$\Gamma$ の 例 $I$ とは、変数の有限集合 $V$ と、制約 $R(v_1,\dots,v_n)$($R\in\Gamma$ は $n$ 項、$v_1,\dots,v_n\in V$。同じ変数が繰り返し現れてよい)の有限の列の組である。写像 $s:V\to D$ が $I$ の 解 であるとは、すべての制約について $(s(v_1),\dots,s(v_n))\in R$ となることをいう。
例が解をもつかを判定する問題を $\mathrm{CSP}(\Gamma)$ と書き、$\Gamma$ を鋳型とする 制約充足問題 という。

例の大きさは変数と制約の個数で測る。割り当てを証明書とすれば $\mathrm{CSP}(\Gamma)$ は NP に属する。
$\Gamma=\{R_1,\dots,R_p\}$ を関係構造 $\mathbf D=(D;R_1,\dots,R_p)$ とみると、$I$ の解は、制約の変数の組を関係とする $V$ 上の関係構造から $\mathbf D$ への準同型と同じものである(BKW17 §2.4, p. 6)。$\Gamma$ が 1 つの対称な 2 項関係なら、これは グラフ準同型 の存在の問題である。

対応を開く

$R_i(v_1,\dots,v_n)$ が制約にあるとき $(v_1,\dots,v_n)\in R_i^{\mathbf I}$ とおいて $V$ 上の関係構造 $\mathbf I$ を作る。写像 $s:V\to D$ が各 $R_i$ を保つこと($\mathbf I\to\mathbf D$ の準同型)は、$s$ が各制約を満たすことと同じである。逆に関係構造 $\mathbf I$ からは、その関係の元ごとに制約を置いて例が得られる。

代表的な例
  1. $k$ 彩色:$D=\{0,\dots,k-1\}$、$\Gamma=\{\ne_k\}$($\ne_k=\{(a,b)\mid a\ne b\}$)。制約 $u\ne_kv$ を辺とするグラフの $k$ 彩色可能性の問題で、$k=2$ では多項式時間で解け、$k\ge3$ では NP完全である(NP完全 の系「$k$ 彩色可能性」と命題「2 彩色可能性の判定」)。
  2. 3SAT:$S_{abc}:=\{0,1\}^3\setminus\{(a,b,c)\}$、$\Gamma_{3}:=\{S_{abc}\mid a,b,c\in\{0,1\}\}$。$\mathrm{CSP}(\Gamma_3)$ は 3SAT と同じ問題で、NP完全である(NP完全 の定理「3SAT の NP完全性」)。
    節の書き直しを開く

    高々 3 個のリテラルの節 $\ell_1\vee\ell_2\vee\ell_3$(足りなければリテラルを繰り返す)は、$\ell_j$ が $x$ なら $a_j=0$、$\neg x$ なら $a_j=1$ として $S_{a_1a_2a_3}$ の制約に書ける。各リテラルが偽になる値の組だけを除くからである。逆に $S_{abc}$ の制約はこの形の節である。

  3. Horn 節:$\Gamma_{\mathrm{Horn}}:=\{S_{110},S_{111},\{0\},\{1\}\}$。$S_{110}$ は $\neg x\vee\neg y\vee z$、$S_{111}$ は $\neg x\vee\neg y\vee\neg z$ で、肯定のリテラルは高々 1 個である(BKW17 Example 5, p. 4)。
  4. 2 元の一次方程式:$D=\mathbb F_2$、$\Gamma_{\mathrm{lin}}:=\{\{(x,y,z)\mid x+y+z=c\}\mid c\in\mathbb F_2\}$。
  5. 2SAT:$\{0,1\}$ 上の空でない 2 項関係の全体。

原始正の定義と還元

原始正の定義

$D$ 上の制約言語 $\Gamma$ と関係 $R\subseteq D^n$ について、$\Gamma\cup\{=_D\}$ の例 $I$($=_D$ は $D$ 上の等号)と、$I$ の相異なる変数 $x_1,\dots,x_n$ があって
$$ R=\{(s(x_1),\dots,s(x_n))\mid s\text{ は }I\text{ の解}\} $$
となるとき、$R$ は $\Gamma$ から 原始正に定義できる という。$\Delta$ の関係がすべて $\Gamma$ から原始正に定義できるとき、$\Gamma$ は $\Delta$ を原始正に定義するという。

論理式で書けば、$R(x_1,\dots,x_n)$ が $\exists y_1\cdots\exists y_m\,(\phi_1\wedge\dots\wedge\phi_l)$(各 $\phi_i$ は $\Gamma$ の関係か等号に変数を入れた原子論理式)と同値になることである(BKW17 Definition 11, p. 7)。

例を開く

$\{0\}(x)$ は $S_{111}(x,x,x)$、$\{1\}(x)$ は $S_{000}(x,x,x)$ で定義されるので、$\Gamma_3$ は $\Gamma_{\mathrm{Horn}}$ を原始正に定義する。

原始正の定義は還元を与える

$D$ 上の制約言語 $\Gamma,\Delta$ について、$\Gamma$ が $\Delta$ を原始正に定義するなら、$\mathrm{CSP}(\Delta)$ は $\mathrm{CSP}(\Gamma)$ に多項式時間で還元できる。

制約を部品に置き換える

各 $R\in\Delta$ について、def-csp-pp の例 $I_R$ と変数 $x^R_1,\dots,x^R_n$ を 1 組固定する。$\Delta$ は有限なので、これらの大きさは定数である。
$\mathrm{CSP}(\Delta)$ の例 $J$(変数の集合 $V$)が与えられたとする。$J$ の各制約 $C=R(v_1,\dots,v_n)$ について $I_R$ の写しを 1 つ作り、$x^R_i$ を $v_i$ に置き換え、ほかの変数は $C$ ごとに新しい変数にする。これらの写しをすべて並べた $\Gamma\cup\{=_D\}$ の例を $J'$ とする。
$J$ が解 $s$ をもつとする。各制約 $C$ で $(s(v_1),\dots,s(v_n))\in R$ だから、$I_R$ の解 $t_C$ で $t_C(x^R_i)=s(v_i)$ となるものがある。$v_i=v_j$ のときも $t_C(x^R_i)=s(v_i)=t_C(x^R_j)$ なので、置き換えと矛盾しない。$V$ の上では $s$、$C$ の写しの新しい変数の上では $t_C$ とすれば、$J'$ の解になる。逆に $J'$ の解 $s'$ を $C$ の写しに制限すると $I_R$ の解になるので、$(s'(v_1),\dots,s'(v_n))\in R$ であり、$s'|_V$ は $J$ の解である。よって $J$ と $J'$ の答えは一致する。
最後に、等号の制約 $u=_Dw$ でつながる変数を 1 つの変数にまとめ、等号の制約を消した $\Gamma$ の例を $J''$ とする。$J'$ の解は等号でつながる変数の上で定数なので、$J'$ の解と $J''$ の解は 1 対 1 に対応する。$J''$ の大きさは $J$ の大きさの定数倍以下で、まとめる操作も多項式時間でできる。$\square$

多相写像

多相写像

$k\ge1$ とし、$f:D^k\to D$ を $k$ 変数の演算とする。$R\subseteq D^n$ の元 $r^1,\dots,r^k$ に対し、座標ごとに当てた
$$ f(r^1,\dots,r^k):=\bigl(f(r^1_1,\dots,r^k_1),\ \dots,\ f(r^1_n,\dots,r^k_n)\bigr) $$
がつねに $R$ に入るとき、$f$ は $R$ を 保つ という。$\Gamma$ のすべての関係を保つ演算を $\Gamma$ の 多相写像 といい、その全体を $\mathrm{Pol}(\Gamma)$、そのうち $k$ 変数のものの全体を $\mathrm{Pol}_k(\Gamma)$ と書く。

射影 $\pi^k_i(a_1,\dots,a_k)=a_i$ はどの関係も保ち、多相写像の合成は多相写像なので、$\mathrm{Pol}(\Gamma)$ はクローン(射影を含み合成で閉じた演算の集まり)である。1 変数の多相写像は $\mathbf D$ の自己準同型である(BKW17 §4.1–4.2, pp. 12–14)。
$s_1,\dots,s_k$ が例 $I$ の解で $f\in\mathrm{Pol}_k(\Gamma)$ なら、$v\mapsto f(s_1(v),\dots,s_k(v))$ も解である(制約ごとに $f$ を値の組に当てたものになる)。

原始正に定義した関係は保たれる

$f\in\mathrm{Pol}(\Gamma)$ は、$\Gamma$ から原始正に定義できるどの関係も保つ。

解に座標ごとに当てる

$R$ を def-csp-pp の $I$ と $x_1,\dots,x_n$ で定義し、$r^1,\dots,r^k\in R$ とする。$I$ の解 $s_j$ で $r^j=(s_j(x_1),\dots,s_j(x_n))$ となるものをとる。$s:=f(s_1,\dots,s_k)$ を変数ごとに定めると、$\Gamma$ の関係の制約は $f$ が保ち、等号の制約はどの演算でも保たれるので、$s$ は $I$ の解である。よって $f(r^1,\dots,r^k)=(s(x_1),\dots,s(x_n))\in R$。$\square$

多相写像による原始正の定義の判定

$\Gamma$ を $D$ 上の制約言語とし、$R=\{r^1,\dots,r^k\}\subseteq D^n$ を $k$ 個の元からなる空でない関係とする。次は同値である。

  1. $R$ は $\Gamma$ から原始正に定義できる。
  2. $\Gamma$ のすべての多相写像が $R$ を保つ。
  3. $\Gamma$ の $k$ 変数の多相写像がすべて $R$ を保つ。

Geiger(1968)と Bodnarchuk ほか(1969)の Galois接続 に由来する(BKW17 Theorem 32, p. 14)。

多相写像の全体を 1 つの関係として定義する

1 ⇒ 2 は lem-csp-preserved、2 ⇒ 3 は明らかである。3 ⇒ 1 を示す。
変数 $w_a$($a\in D^k$)をもつ $\Gamma$ の例 $P_k$ を次のように作る。各 $S\in\Gamma$($m$ 項)と、$D^k$ の点の組 $(a^1,\dots,a^m)$ で、どの $j=1,\dots,k$ についても $(a^1_j,\dots,a^m_j)\in S$ となるものすべてについて、制約 $S(w_{a^1},\dots,w_{a^m})$ を置く。写像 $f:D^k\to D$ と割り当て $w_a\mapsto f(a)$ を同一視すると、$f$ が $P_k$ の解であることは、$S$ の $k$ 個の元 $t^j=(a^1_j,\dots,a^m_j)$ に $f$ を座標ごとに当てた $(f(a^1),\dots,f(a^m))$ がつねに $S$ に入ること、すなわち $f\in\mathrm{Pol}_k(\Gamma)$ と同値である。
$R$ の元を行に並べた $k\times n$ 行列の第 $i$ 列を $c_i:=(r^1_i,\dots,r^k_i)\in D^k$ とする。$P_k$ に新しい変数 $x_1,\dots,x_n$ と等号の制約 $x_i=w_{c_i}$ を足した例で $x_1,\dots,x_n$ を選ぶと、定義される関係は
$$ R':=\{(f(c_1),\dots,f(c_n))\mid f\in\mathrm{Pol}_k(\Gamma)\}=\{f(r^1,\dots,r^k)\mid f\in\mathrm{Pol}_k(\Gamma)\} $$
である。射影 $\pi^k_j$ から $r^j\in R'$ なので $R\subseteq R'$。3 により $f(r^1,\dots,r^k)\in R$ なので $R'\subseteq R$。よって $R=R'$ は原始正に定義できる。$\square$

計算量は多相写像で決まる

$D$ 上の制約言語 $\Gamma,\Delta$ が $\mathrm{Pol}(\Gamma)\subseteq\mathrm{Pol}(\Delta)$ を満たすなら、$\mathrm{CSP}(\Delta)$ は $\mathrm{CSP}(\Gamma)$ に多項式時間で還元できる。とくに $\mathrm{CSP}(\Gamma)$ の計算量は $\mathrm{Pol}(\Gamma)$ だけで決まる(BKW17 p. 15)。

$\Delta$ の各関係は $\mathrm{Pol}(\Gamma)$ のすべての元で保たれるので、thm-csp-galois により $\Gamma$ から原始正に定義でき、thm-csp-reduction を当てればよい。$\square$

3SAT の多相写像は射影だけ

$\mathrm{Pol}(\Gamma_3)$ は射影だけからなる(BKW17 Example 33, p. 15 が演習とするもの)。

証明を開く

$f\in\mathrm{Pol}_k(\Gamma_3)$ とする。$S_{100}(x,y,y)$ は $x\le y$、$S_{000}(x,y,y)$ は $x\vee y$、$S_{111}(x,y,y)$ は $\neg(x\wedge y)$ を定義し、後の 2 つの共通部分は $\ne_2$ である。lem-csp-preserved により $f$ はこれらと $S_{000}$ を保つ。$S\subseteq[k]$ の指示ベクトルを $1_S$ とし、$\mathcal W:=\{S\mid f(1_S)=1\}$ とおく。$\le$ を保つので $\mathcal W$ は上に閉じ、$\ne_2$ を保つので $f(1_{[k]\setminus S})=1-f(1_S)$、つまり $S$ と補集合のちょうど一方が $\mathcal W$ に入る。$S_{000}$ を保つことを、和集合が $[k]$ になる $A,B,C$ について、第 $j$ 行が $(1_A(j),1_B(j),1_C(j))\in S_{000}$ である $k\times3$ 行列に当てると、$f(1_A),f(1_B),f(1_C)$ のどれかは $1$ である。補集合をとれば、$\mathcal W$ のどの 3 元(重複を許す)も共通部分が空でない。$\emptyset$ と $[k]$ の一方は $\mathcal W$ に入るので $\mathcal W$ は空でなく、極小元 $X$ がある。$X=\emptyset$ なら上に閉じることから $\mathcal W$ はすべての部分集合を含み、補集合の一方だけが入ることに反する。$\#X\ge2$ と仮定して $X=X_1\sqcup X_2$(どちらも空でない)と分けると、極小性から $X_1,X_2\notin\mathcal W$ なので補集合が $\mathcal W$ に入り、$X\cap([k]\setminus X_1)\cap([k]\setminus X_2)=\emptyset$ となって矛盾する。よって $X=\{i\}$。$i\in S$ なら $S\in\mathcal W$、$i\notin S$ なら $S\subseteq[k]\setminus\{i\}\notin\mathcal W$ なので $S\notin\mathcal W$。従って $f(1_S)=[i\in S]$、すなわち $f=\pi^k_i$ である。

多相写像があると易しくなる場合

半束の演算と弧整合

2 変数の演算 $\wedge$ が冪等($a\wedge a=a$)・可換・結合的のとき 半束演算 という。空でない有限集合 $A\subseteq D$ の元すべての $\wedge$ を $\bigwedge A$ と書く(順序によらない)。全順序集合の $\min$ がその例である。
例 $I$ の 弧整合の手続き を次のように定める。各変数 $v$ に $D_v:=D$ を割り当て、次の操作ができなくなるまで繰り返す:制約 $R(v_1,\dots,v_n)$ と $i$ と $a\in D_{v_i}$ で、$t\in R$、$t_i=a$、すべての $j$ で $t_j\in D_{v_j}$、かつ $v_j=v_l$ なら $t_j=t_l$、を満たす $t$(支え)がないものがあれば、$a$ を $D_{v_i}$ から除く。値を除くたびに $\sum_v\#D_v$ が減るので、操作は $\#V\cdot\#D$ 回以下で終わり、手続きは多項式時間である。
$s$ が $I$ の解なら、$(s(v_1),\dots,s(v_n))$ はつねに $s(v_i)$ の支えなので、$s(v)$ は $D_v$ から除かれない。従って手続きの後にある $D_v$ が空なら、$I$ は解をもたない。

半束の多相写像があれば弧整合で解ける

半束演算 $\wedge$ が $\Gamma$ の多相写像なら、弧整合の手続きの後ですべての $D_v$ が空でないとき、$s(v):=\bigwedge D_v$ は $I$ の解である。従って $\mathrm{CSP}(\Gamma)$ は多項式時間で解ける。

支えの全体の $\wedge$ をとる

手続きの後の制約 $R(v_1,\dots,v_n)$ を 1 つとる。各 $i$ と $a\in D_{v_i}$ について支え $t^{(i,a)}$ がある。これらの有限個の元の $\wedge$ を座標ごとにとった $t$ は、$\wedge$ が $R$ を保つので $R$ に入る。第 $i$ 座標は、$t^{(i,a)}_i=a$($a\in D_{v_i}$)をすべて含み $D_{v_i}$ に含まれる集合の $\bigwedge$ なので、$\bigwedge D_{v_i}=s(v_i)$ である。よって $(s(v_1),\dots,s(v_n))=t\in R$。どの支えも $v_j=v_l$ なら第 $j$・第 $l$ 座標が等しいので、変数が繰り返す場合もこれは矛盾しない。$\square$

$\Gamma_{\mathrm{Horn}}$ は $\min$ で保たれる(BKW17 Example 28, p. 13)ので、Horn 節の充足可能性は thm-csp-semilattice により多項式時間で解ける。

理由を開く

$\min(r,r')=(1,1,0)$ なら、$r,r'$ は第 1・第 2 座標がともに $1$ で、第 3 座標が $0$ の方は $(1,1,0)$ である。$(1,1,1)$ も同様で、$\{0\},\{1\}$ は冪等性から保たれる。

アフィンな関係

少数決の演算とアフィン部分空間

$D=\mathbb F_2$ とし、$\mu(x,y,z):=x+y+z$ とする。

  1. 空でない $R\subseteq\mathbb F_2^n$ が $\mu$ で保たれることと、$R$ がアフィン部分空間(線形部分空間 $L$ と $r_0$ による $r_0+L$)であることは同値である。
  2. $\mu\in\mathrm{Pol}(\Gamma)$ なら $\mathrm{CSP}(\Gamma)$ は多項式時間で解ける。
連立一次方程式に直す
  1. $R=r_0+L$ なら、$a,b,c\in R$ について $a+b+c=r_0+\bigl((a-r_0)+(b-r_0)+(c-r_0)\bigr)+2r_0$ で $2r_0=0$ だから $\mu(a,b,c)\in R$。逆に $R$ が $\mu$ で保たれるとし、$r_0\in R$、$L:=R-r_0$ とおく。$u=a-r_0$、$w=b-r_0$($a,b\in R$)について $u+w+r_0=a+r_0+b=\mu(a,r_0,b)\in R$ なので $u+w\in L$。$0\in L$ なので $L$ は加法で閉じた $\mathbb F_2^n$ の部分集合、すなわち線形部分空間である。
  2. 各 $R\in\Gamma$ はアフィン部分空間なので、行列 $A_R$ とベクトル $b_R$ で $R=\{x\mid A_Rx=b_R\}$ と書ける。$\Gamma$ は固定なのでこれらは定数である。例の制約 $R(v_1,\dots,v_n)$ を $A_R(v_1,\dots,v_n)^{\mathsf T}=b_R$ に置き換えると(繰り返す変数はそのまま同じ未知数とする)、例は未知数が変数の個数、式が制約の個数の定数倍の $\mathbb F_2$ 上の連立一次方程式になり、解の存在は Gauss消去法 で多項式時間で判定できる。$\square$

$\mu$ を 少数決 という。$\Gamma_{\mathrm{lin}}$ は $\mu$ で保たれる。

名前と $\mathbb F_p$ の場合を開く

$\mu$ は 2 つの引数が等しければ残りの 1 つを返す。$\Gamma_{\mathrm{lin}}$ の関係はアフィン部分空間なので thm-csp-affine の 1 により $\mu$ で保たれる。$\mathbb F_p$ では $x-y+z$ が同じ役割を果たす(BKW17 Example 29, p. 13)。

多数決の演算

$\{0,1\}$ 上の 多数決 $\mathrm{maj}(x,y,z)$ は 3 つの引数のうち 2 つ以上がとる値を返し、$\{0,1\}$ 上の 2 項関係をすべて保つ(BKW17 Example 26, p. 12)。

理由を開く

$3\times2$ の 0/1 行列の各列に $\mathrm{maj}$ を当てた組は、どれかの行に等しい。各列で多数派の値をとる行は 2 行以上あり、3 行の中で重なるからである。

一般に多数決型の多相写像($f(x,x,y)=f(x,y,x)=f(y,x,x)=x$)をもつ $\Gamma$ では、変数の 2 つ組と 3 つ組についての局所的な整合性の手続きが解の存在を判定し、$\mathrm{CSP}(\Gamma)$ は多項式時間で解ける(BKW17 Theorem 61, p. 29。この記事では証明しない)。とくに 2SAT は多項式時間で解ける。

Schaefer の二分定理

定数の関係を足しても難しくならない

$\Gamma$ の 1 変数の多相写像がすべて全単射であるとする。このとき $\Gamma^+:=\Gamma\cup\{\{a\}\mid a\in D\}$ について、$\mathrm{CSP}(\Gamma^+)$ は $\mathrm{CSP}(\Gamma)$ に多項式時間で還元できる。

自己準同型で解を戻す

prf-csp-galois の例 $P_1$(変数 $w_d$、$d\in D$)をとる。その解は 1 変数の多相写像 $h$($w_d\mapsto h(d)$)と同じものである。$\mathrm{CSP}(\Gamma^+)$ の例 $J$ について、$P_1$ の写しを $J$ と変数を共有しないように足し、各制約 $\{a\}(x)$ を等号の制約 $x=w_a$ に置き換え、prf-csp-reduction の最後と同じく等号でつながる変数をまとめた $\Gamma$ の例を $J^*$ とする。大きさは $J$ の大きさに定数を足したもの以下である。$J^*$ の解は、等号の制約を残した例の解で等号でつながる変数の上で定数なものと同じなので、以下では等号の制約を残した形で考える。
$J$ の解 $s$ があれば、$w_d\mapsto d$(恒等写像)と合わせたものが $J^*$ の解になる。逆に $J^*$ の解 $s^*$ があれば、$h(d):=s^*(w_d)$ は 1 変数の多相写像なので、仮定により全単射である。$D$ の置換の群は有限なので $h^N=\mathrm{id}$ となる $N\ge1$ があり、$h^{-1}=h^{N-1}$ も多相写像である。$s:=h^{-1}\circ s^*$ は $\Gamma$ の制約と等号の制約をすべて満たし(多相写像は解を解に写す)、$s(w_a)=h^{-1}(h(a))=a$ だから、$x=w_a$ により $s(x)=a$ で $\{a\}(x)$ も満たす。よって $J$ と $J^*$ の答えは一致する。$\square$

1 変数の多相写像がすべて全単射である $\Gamma$ を コア という(BKW17 Theorem 17, p. 9。グラフでは グラフ準同型 の定義「準同型同値とコア」)。
$\mathrm{Pol}(\Gamma^+)$ は $\Gamma$ の多相写像のうち 冪等($f(a,\dots,a)=a$)なものの全体である。$\{a\}$ を保つことが $f(a,\dots,a)=a$ と同じだからである。

Post の分類から従う補題

$\{0,1\}$ 上の冪等な演算からなるクローンが射影でない演算を含めば、それは 2 変数の $\max$、2 変数の $\min$、多数決 $\mathrm{maj}$、少数決 $\mu$ のどれかを含む。

補題の出典

この補題は Post による $\{0,1\}$ 上のクローンの分類から従い、分類の全体を使わない直接の証明の方針も知られている(BKW17 Lemma 62, pp. 29–30)。この記事では証明しない。

Schaefer の二分定理

$\Gamma$ を $\{0,1\}$ 上の制約言語とする。$\Gamma$ が次の 6 つの演算のどれかを多相写像にもつなら $\mathrm{CSP}(\Gamma)$ は多項式時間で解け、どれももたないなら $\mathrm{CSP}(\Gamma)$ は NP完全である。

  • 定数 $0$、定数 $1$(1 変数)、
  • $\min$、$\max$、
  • 多数決 $\mathrm{maj}$、少数決 $\mu(x,y,z)=x+y+z$。

Schaefer(Sch78)はこの分類を関係の形の言葉で述べた。多相写像を使う下の証明は BKW17 Theorem 63, p. 30 による。

関係の形との対応を開く

BKW17 p. 30 は、$\min$ で保たれる $\Gamma$ は $\Gamma_{\mathrm{Horn}}$ から($\max$ はその双対)、$\mathrm{maj}$ で保たれる $\Gamma$ は 2 項関係の全体から、$\mu$ で保たれる $\Gamma$ は 3 変数の一次方程式の全体から原始正に定義できることを演習として挙げている。3 変数の一次方程式は $\Gamma_{\mathrm{lin}}$ から原始正に定義できる($x+x+x=x$ で定数が作れる)。

易しい場合と、射影だけの場合

易しい側。1 変数の定数 $a$ が $R$ を保つなら、$R$ は空でないので $(a,\dots,a)\in R$ であり、すべての変数に $a$ を割り当てればどの例も解ける。$\min$ と $\max$ は $\{0,1\}$ の 2 通りの全順序の半束演算なので thm-csp-semilattice、$\mu$ は thm-csp-affine、$\mathrm{maj}$ は前節で引用した結果による。
難しい側。6 つのどれも多相写像でないとする。$\{0,1\}$ 上の 1 変数の演算は定数 2 つと恒等写像と $x\mapsto1-x$ なので、1 変数の多相写像はすべて全単射であり、$\Gamma$ はコアである。$\mathrm{Pol}(\Gamma^+)$ は冪等な演算のクローンで、射影でない演算を含めば lem-csp-post により $\max,\min,\mathrm{maj},\mu$ のどれかを含むが、それは $\Gamma$ の多相写像になって仮定に反する。よって $\mathrm{Pol}(\Gamma^+)$ は射影だけからなる。射影はどの関係も保つので、thm-csp-galois により $\Gamma^+$ は $\{0,1\}$ 上の空でない関係をすべて、とくに $\Gamma_3$ を原始正に定義する。thm-csp-reduction と lem-csp-core により
$$ \text{3SAT}=\mathrm{CSP}(\Gamma_3)\ \le\ \mathrm{CSP}(\Gamma^+)\ \le\ \mathrm{CSP}(\Gamma) $$
($\le$ は多項式時間の還元)であり、3SAT は NP完全で $\mathrm{CSP}(\Gamma)$ は NP に属するので、$\mathrm{CSP}(\Gamma)$ は NP完全である。$\square$

$\{0,1\}$ 上の制約充足問題には、多項式時間で解けず NP完全でもない中間のものがない。

中間の問題について開く

$\mathrm{P}\ne\mathrm{NP}$ なら、NP には多項式時間で解けず NP完全でもない問題があることが知られている(Ladner、1975 年。BKW17 p. 5)。この定理は、$\{0,1\}$ 上の制約充足問題の中にはそれが現れないことを述べている。

一般の有限集合の上の二分定理

$k\ge2$ 変数の演算 $f$ が
$$ f(y,x,\dots,x)=f(x,y,x,\dots,x)=\dots=f(x,\dots,x,y)\qquad(x,y\in D) $$
を満たすとき 弱全会一致演算 という(BKW17 p. 18)。多数決と少数決($k=3$)、半束演算($k=2$)はその例である。

制約充足問題の二分定理

$D$ 上の制約言語 $\Gamma$ が弱全会一致演算を多相写像にもつなら $\mathrm{CSP}(\Gamma)$ は多項式時間で解け、もたないなら NP完全である。

二分定理の出典

多項式時間の側は Bulatov(Bul17)と Zhuk(Zhu20 Theorem 1.4)がそれぞれ別のアルゴリズムで示した。この記事では証明しない。

NP完全の側の出典を開く

NP完全の側は、Jeavons・Cohen・Gyssens(1997)に始まる代数的な方法(とくに Bulatov・Jeavons・Krokhin(2005))と、Taylor(1977)の定理、Maróti・McKenzie(2008)の弱全会一致演算の存在定理から従う(BKW17 Theorems 40–41・Corollary 42, p. 18、Zhu20 Theorem 1.3)。

thm-csp-schaefer は $D=\{0,1\}$ の場合である。

同値な条件とグラフの場合を開く

弱全会一致演算をもつことは、4 変数の演算で $f(y,x,y,z)=f(x,y,z,x)$ を満たすもの(Siggers 演算)をもつこと、巡回演算をもつことなどと同値である(BKW17 Theorem 41, p. 18)。$\Gamma$ が 1 つの対称な 2 項関係(グラフ $H$)からなる場合は、Hell と Nešetřil が 1990 年に、$H$ がループをもつか二部グラフなら多項式時間で解け、そうでなければ NP完全であることを示していた(BKW17 p. 5。巡回演算を使う証明の方針が Example 45, p. 19 にある)。

例と反例

原始正に定義できる関係とできない関係

$D=\{0,1\}$、$\Gamma=\{\le\}$ とする。$\mathrm{Pol}(\Gamma)$ は単調な演算の全体である。$\{(x,y,z)\mid x\le y\le z\}$ は $x\le y\wedge y\le z$ で定義される。一方 $\ne_2$ は定数 $0$(単調)で保たれないので、thm-csp-galois により $\{\le\}$ から原始正に定義できない。

構成で確かめる

prf-csp-galois の構成を $\ne_2=\{(0,1),(1,0)\}$ に当てると、列は $c_1=(0,1)$、$c_2=(1,0)$ で、2 変数の単調な演算の値 $(f(0,1),f(1,0))$ は定数で $(0,0),(1,1)$、射影で $(0,1),(1,0)$ をとるので、$R'=\{0,1\}^2\supsetneq\ne_2$ となる。

反例:多数決は 3SAT の関係を保たない

$(0,1,1),(1,0,1),(1,1,0)\in S_{111}$ に $\mathrm{maj}$ を座標ごとに当てると $(1,1,1)\notin S_{111}$ になる(BKW17 p. 14)。

反例:射影でない多相写像があっても NP完全になりうる

$\varphi:\{0,1,2\}\to\{0,1\}$ を $\varphi(0)=0$、$\varphi(1)=\varphi(2)=1$ とし、$\Gamma':=\{\varphi^{-1}(S)\mid S\in\Gamma_3\}$($\varphi^{-1}(S)$ は座標ごとに $\varphi$ を当てて $S$ に入る組の全体)を $\{0,1,2\}$ 上の制約言語とする(BKW17 Example 44, p. 19)。

  1. $\mathrm{CSP}(\Gamma')$ は NP完全である。
  2. $g(x,y):=y$($x,y\in\{1,2\}$ のとき)、$g(x,y):=x$(それ以外)は $\Gamma'$ の多相写像で、射影でない。
    1 と 2 の確かめを開く

    1:$\Gamma'$ の例の解 $s$ から $\varphi\circ s$ は対応する 3SAT の例の解になり、3SAT の解は $\{0,1\}\subseteq\{0,1,2\}$ への値として $\Gamma'$ の例の解である。よって 2 つの例の答えは一致する。2:$r,r'\in\varphi^{-1}(S)$ について、$r_i=0$ なら $g(r_i,r'_i)=0$、$r_i\in\{1,2\}$ なら $g(r_i,r'_i)\in\{1,2\}$ なので、$\varphi(g(r,r'))=\varphi(r)\in S$ である。$g(1,2)=2$、$g(1,0)=1$ なので $g$ はどちらの射影でもない。

    $g$ は冪等なので、定数の関係を足しても多相写像のまま残る。従って「冪等で射影でない多相写像があれば易しい」は 3 元の集合の上では成り立たず、lem-csp-post は 2 元の集合に特有である(BKW17 pp. 18–19)。
    詳しく開く

    $g(a,a)=a$ なので $g$ は $\{0\},\{1\},\{2\}$ を保ち、$\Gamma'\cup\{\{0\},\{1\},\{2\}\}$ の問題は NP完全のままである(BKW17 p. 19)。$g(1,0)=1\ne0=g(0,1)$ なので $g$ は弱全会一致演算でない。thm-csp-dichotomy が射影でないことではなく恒等式を課すのはこのためである。

3 彩色と 2 彩色

$\ne_2$ は $\mathrm{maj}$ で保たれる。一方 $\{0,1,2\}$ 上の多数決型の演算 $f$($f(x,x,y)=f(x,y,x)=f(y,x,x)=x$)はどれも $\ne_3$ を保たない。

理由を開く

$\sigma=(\sigma_1,\sigma_2,\sigma_3)$ を $0,1,2$ の並べ替えとすると、$f(\sigma)=\sigma_i$ となる $i$ がある。$v:=\sigma_i$ とし、第 $i$ 成分だけ $v$ と異なる値 $y$、ほかの成分が $v$ の列 $c$ をとる。各 $j$ で $c_j\ne\sigma_j$($j\ne i$ では $\sigma_j\ne\sigma_i=v$、$j=i$ では $y\ne v$)なので、行 $(c_j,\sigma_j)$ はすべて $\ne_3$ に入る。ところが $f(c)=v=f(\sigma)$ なので、$f$ を当てた組 $(v,v)$ は $\ne_3$ に入らない。$\mathrm P\ne\mathrm{NP}$ なら、3 彩色が NP完全であること(NP完全)と thm-csp-dichotomy から、$\ne_3$ は弱全会一致演算を一つも多相写像にもたない。

主張反例満たされない条件
冪等で射影でない多相写像があれば多項式時間で解けるex-csp-quotient集合が 2 元であること(lem-csp-post)、一般には弱全会一致の恒等式
2SAT を解く多数決の方法は 3SAT にも使えるex-csp-maj-3sat関係が 2 項であること
$\{\le\}$ は $\{0,1\}$ 上のすべての関係を原始正に定義する$\ne_2$(ex-csp-le)すべての多相写像(ここでは定数 $0$)で保たれること
2 項関係だけの言語は 3 元の集合の上でも多数決型の多相写像をもつ$\ne_3$(ex-csp-coloring)集合が 2 元であること($\ne_2$ は $\mathrm{maj}$ で保たれる)

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する