数理解析研究所講究録
第 1873 巻 2014 年 98-101

98
$NP$

完全問題の行列表現

富山化学工業株式会社 松木 伯元
Norichika Matsuki
Toyama Chemical Co., Ltd.

1. はじめにが $\{0,1\}\cross\cdots\cross\{0,1\}$ に零点をもつか判定する問題を考えよう$f(x_{1},\ldots,x_{n})\in Q[x_{1},\ldots,x_{n}]$(本稿ではこの問題を 0-lSOL と省略して呼ぶことにする) 0-lSOL は代表的な $NP$
完全問題である 3-SAT[1] を特殊な場合として含む。 なぜなら 3-SAT は。

$f(x_{1},\ldots,x_{n})=y_{l1}y_{12}y_{l3}+\cdots+y_{m}1y_{m}2y_{m}3 (y_{11},\ldots,y_{m}1\in\{x_{1},1-x_{1},\ldots,x_{n},1-x_{n}\})$

とおいた場合と同値だからである [2]。そのため計算複雑性が $NP$ に属する問題はすべて 0-1 SOL の形式で表されるが、 残念ながら 0-1 SOL を効率良く解くためのアルゴリズムは存在しないと強く予想されている ( $P\neq NP$ 予想)。
が本稿では、 まず 0-lSOL を環論的に特徴づけ、 表現論を通じて$f(X_{1},\ldots,xn)$$\cdots\cross\{0,1\}$$\{0,1\}\cross$に零点をもっための必要十分条件が行列式で与えられることを示す。そして0-1 SOL を変数変換した問題であるをもつか判定する問題 (これを$\pm$$f(x_{1},\ldots,x_{n})\in Q[x_{1},\ldots,x_{n}]$が $\{-1,1\}\cross\cdots\cross\{-1,1\}$ に零点ISOL と呼ぶことにする) に対しても同様なことが成り立つことにふれる。

2. 0-lSOL の代数的特徴$I_{n}=(x_{1}(1-x_{1}),\ldots,x_{n}(1-x_{n}))\subset Q[x_{1},\ldots,x_{n}]$をイデアルとする。このとき次が成り立つ (証明は [3] 参照)。

補題 1 任意の$c_{1},\ldots,c_{n}\in\{0,1\}$に対して $f(c_{1},\ldots,c_{n})=0$ であるためには、$f(x_{1},\ldots,x_{n})\equiv 0$(mod )$I_{n}$が成り立つことが必要十分である。
これから次の補題が導かれる。

補題 2$f(x_{1},\ldots,x_{n})\in Q[x_{1},\ldots,x_{n}]$が $\{0,1\}\cross\cdots\cross\{0,1\}$ に零点をもつためには、 f(xl,の零元か零因子であることが必要十分である。となる点 (Cl, ,Cn) {0,1}
証明 十分性 :$\ldots$,xn) が$Q[x_{1},\ldots,x_{n}]/I_{n}$$f(x_{1},\ldots,x_{n})\neq 0$$+(x_{n}-c_{n})^{2})$$\in$$\cross$$\ldots$$\cross\{0,1\}$に対して $\Pi((x_{1}-c_{1})^{2}+$をとれば$f(x_{1},\ldots,x_{n})\Pi((x_{1}-c_{1})^{2}+\cdots+(x_{n}-c_{n})^{2})\equiv 0$

必要性 : $f(x_{1},\ldots,xn)$ が$Q[x_{1},\ldots,x_{n}]/I_{n}$(mod )$I_{n}$の零因子であれば、 補題 1 からに零点をもたなければならいことが分かる。

$\{0,1\}\cross\cdots\cross\{0,1\}$

99
補題 3

$f(x\iota,\ldots,x_{n})\in Q[x\downarrow,\ldots,x_{n}]$が $\{0,1\}\cross\cdots\cross\{0,1\}$ に零点をもたないためには、$f(x_{1},\ldots,x_{n})$が $Q[x_{1},\ldots,x_{n}]/I_{n}$ の可逆元であることが必要十分である。

証明 $f(x_{1},\ldots,Xn)$ が $\{0,1\}\cross\cdots\cross\{0,1\}$ に零点をもたないとき、$\Sigma(1-(x_{1}-c_{1})^{2})\cdots(1-(x_{n}-c_{n})^{2})/f(c_{1},\ldots,c_{n})$がその逆元である。 逆は補題 2 から$(和はすべての c_{1},\ldots,c_{n}\in\{0,1\} にわたってとる)$

明らか。

3. 0-lSOL の判定式
いま $f0a_{i}x_{i}a_{ij}x_{i}x_{j}+\cdots+a_{1\cdots n}x\iota\ldots x_{n}$ (mod$I_{n}$) に対して、$Q[x_{1},\ldots,x_{n}]/I_{n}$ から$2^{n}$

次行列への写像 $T(f)=(t_{ij})$ を次のように定義する。
$1i\neq j$

ならば$t_{j}=0$$2a_{0},a_{1},\ldots,a_{n},a_{12},a_{13},\ldots,a_{narrow\ln},a_{123},\ldots,a_{1\cdots n}$を次数付辞書式順序に並べて 番目が$i$$a_{i(1)\cdots i(k)}$のとき $t_{ii}=a_{0}+a_{i(1)}+\cdots+a_{i(k)}+a_{i(1)i(2)}+\cdots+a_{i(k-1)i(k)}+\cdots+a_{i(1)\cdots i(k)}$このとき次の性質が容易に導かれる。
補題 4$T$は環準同型である。

そして補題 2,3,4 から直ちに次が従う。
定理 5 $f(x_{1},\ldots,x_{n})\in Q[x_{1},\ldots,x_{n}]$ が $\{0,1\}\cross\cdots\cross\{0,1\}$ に零点をもつためには、 $\det T(f)=0$ であることが必要十分である。
しかしながら $\det T(f)=\Pi f(c_{1},\ldots,c_{n})$$(積はすべての Cl,\ldots,c_{n}\in\{0,1\} にわたってとる)$であるため、 この判定式は有益ではない。

4.

SOL の場合
SOL は 0-lSOL と異なった様相を呈する。 まず$\pm 1$$\pm 1$イデアルとし、$\{j_{1},\ldots j_{q}\},\{k_{1},\ldots,k_{r}\}$に対して演算$\triangle$$J_{n}=(x_{1^{2}}-1,\ldots,x_{n}^{2}-1)\subset Q[x_{1},\ldots,x_{n}]$をを次のように定義する。

$101,\ldots j_{q}\}\triangle\{k_{1},\ldots,k_{r}\}=\{j_{1},\ldots j_{q}\}\cup\{k_{1},\ldots,k_{r}\}-o_{1},\ldots j_{q}\}\cap\{k_{1},\ldots,k_{r}\}$$2\mathfrak{g}_{1},\ldots j_{q}\}\triangle\{0\}=\{0\}\triangle\{j_{1},\ldots j_{q}\}=\{j_{1},\ldots j_{q}\}$$30_{1},\ldots j_{q}\}\triangle t_{1},\ldots j_{q}\}=\{0\}$、さらに$\{0\}\triangle\{0\}=\{0\}$$f\equiv a0+\Sigma a_{i}x_{i}+\Sigma a_{ij}x_{i}x_{j}+\cdots+a_{1\cdots n}x\iota\ldots x_{n}$行列への写像$S(f)=(s_{ij})$$=a_{i(1)\cdots i(k)}$$Q[x\iota,\ldots,x_{n}]\int J_{n}$から$2^{n}$

次を次のように定義する。

$1a_{0},a_{1},\ldots,a_{n},a_{12},a_{13},\ldots,a_{n-\ln},a_{123},\ldots,a_{1\cdots n}$のとき Sli(mod Jn) に対して、を次数付辞書式順序に並べて$i$番目が$a_{i(1)\cdots i(k)}$100(ただし右辺の添え字k(r) ならば△發Slkから記号{、} 、，を除く)
このとき補題 1 4 と同様の性質と、 それゆえ次が成り立つ [4]。
$s_{li^{=aj(1)\cdots j(q)、}}$$Sjk^{=a}\{j(1),\cdots j(q)\}\triangle(k(1),\cdots,k(q)\}$$=a_{k(1)}\ldots$$\sim$

が $\{-1,1\}\cross\cdots\cross\{-1,1\}$ に零点をもつためには、$\det S(f)=0$ で定理 6あることが必要十分である。
$f(x_{1},\ldots,x_{n})\in Q[x_{1},\ldots,x_{n}]$5. 例(1) 5 変数 3-SAT を士 ISOL 型の多項式に変換すると$f(x_{1},\ldots,x_{5})=y_{11}y_{12}y_{13}+\cdots+y_{m1}y_{m2}y_{m3}\equiv a_{0}+\Sigma a_{i}x_{i}+\Sigma a_{ijj}x_{i}x+\cdots+\Sigma$$(y_{1},\ldots,y_{m1}\in\{(1\pm x_{1})/2,\ldots,(1\pm x_{5})/2\})$$S$

aijkxixjxk (mod)$J_{n}$となるから、5 変数 3-SAT に対応する行列式$\det$(t) は次の通りである。

(2)$\pm 1$から成る$n$次正方行列 $H$ で $H^{t}H=nE$ ($E$は単位行列) を満たすものはアダマール行列と呼ばれている。 組合せ論で有名な未解決問題であるアダマール予想は、すべての 4 の倍数 に対してアダマール行列が存在するという予想である (例えば [5] 参照)。
$n$

ここでアダマール行列の存在は$h_{n}=\Sigma_{i<j}(x_{i1}x_{j1}+\cdots+x_{in}x_{jn})^{2}$が $\{-1,1\}\cross\cdots\cross\{-1,1\}$ に零点をもつことと同値であるから、 上記予想を証明するには、

101
すべての 4 の倍数容易ではない。

$n$に対して$\det S(h_{\underline{\mathfrak{n}}})=0$が成り立っことを示せばよい。しかし計算は参考文献[1] S. A. Cook, The complexity of theorem-procedures, in Proceedings of the 3rd ACM

Symposium on Theory of Computing (1971) 151-158.

[2] N. Matsuki, An analytic criterion for CSAT, Inform. Process. Lett., 112 (2012) 164-165.

[3] N. Matsuki, $A$ note on Diophantine equations over finite fields, Univers. J. Math. Math.

Sci. 3 (2013) 105-108.
[4] N. Matsuki, The linear representations ofdecision problems, submitted for publication.
[5] J. Seberry and M. Yamada, Hadamard matrices, sequences, and block design, inContemporary Design Theory, A Collection of Surveys (J. H. Dinitz and D. R. Stinson, eds.),
John Wiley & Sons, New York, 1992, 431-560.