Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

節の長さが $2$ か $3$ かは、小さな違いに見える。本稿は、無作為な論理式で満たせる割合と解く手間を測り、その違いが崖の位置と手間の伸び方の二つに出ることを数える。新しい定理も法則も主張しない。

第一に、二つの解き方は正しい。2-SAT を含意グラフで解いた $200$ 問と、3-SAT を分岐で解いた $100$ 問は、全部の割り当てを試した答えと一致した（第2節）。

第二に、2-SAT の崖は $\alpha$ が $1$ から $1.5$ のあいだで鋭くなる。$\alpha=1.5$ で満たせる割合は、変数 $20$ 個の $0.695$ から $320$ 個の $0.025$ へ落ち、$\alpha=1.0$ では $0.975$・$0.960$・$0.945$ とゆっくり下がる（第2節）。

第三に、3-SAT の崖はもっと右にある。変数 $20$ 個で、$\alpha=4.0$ に $0.850$、$4.25$ に $0.650$、$4.5$ に $0.583$、$5.0$ に $0.283$ である（第2節）。

第四に、これが本稿の芯である。崖の近くで解く手間の伸び方が違う。同じ分岐の解き方で変数を $20$ 個から $40$ 個に倍にすると、平均の分岐は 3-SAT で $\mathbf{3.377358}$ 倍、2-SAT で $\mathbf{1.536885}$ 倍になる（第3節）。

第五に、2-SAT の手間は変数に比例するより遅く、3-SAT は速く伸びる。2-SAT は変数を $8$ 倍にして分岐が $4.569672$ 倍、3-SAT は $4$ 倍にして $7.347015$ 倍である（第3節）。

第六に、分離子は、満たせる割合を見るか、解くのに要る分岐の数を見るかである。どちらにも崖はあるが、崖の上で手間が跳ね上がるのは節が三つのときである（第4節）。

キーワード：充足可能性問題、2-SAT、3-SAT、含意グラフ、分岐、崖。

射程（何を示さないか）

新しい定理も法則も主張しない。2-SAT が含意グラフの強連結成分で手早く解けること、3-SAT が一般には難しい問題とされること、無作為な論理式で満たせる割合が節の比のある値の近くで崩れることは、いずれも既知である。計算量の理論に入らない。P と NP の関係や、難しさの証明には入らない。崖の位置の理論値を主張しない。測ったのは変数 $320$ 個まで（3-SAT は $40$ 個まで）の小さい式の割合で、変数を増やしたときの極限の位置は述べない。速い解き方を論じない。分岐の解き方は手間を数えるための道具で、よい解き方を比べていない。既刊との関係：論文348 は、同じグラフで繋ぐのは安く、並べるのは高いことを示した。本稿はその隣に置く。あちらは同じグラフの上の二つの問いで手間が分かれた。ここでは同じ形の論理式で、節の文字が二つか三つかだけで手間の伸び方が分かれる。加えたのは、二つの解き方を全部の割り当てと突き合わせたこと、変数の数を変えて崖の鋭くなり方を測ったこと、同じ分岐の解き方で変数を倍にしたときの手間 $3.377358$ 倍と $1.536885$ 倍を測ったこと、分離子を「満たせる割合か、分岐の数か」に置いたことである。

1. 記法と問い

設定：変数 $n$ 個、節 $m$ 個の論理式を無作為に作る。一つの節は $k$ 個の異なる変数を選び、それぞれを否定するかどうかを半々で決め、「または」でつなぐ。式は節を「かつ」でつなぐ。

$$\alpha=\frac{m}{n},\qquad
\text{2-SAT}:\ k=2,\qquad \text{3-SAT}:\ k=3$$

2-SAT は含意グラフの強連結成分で、3-SAT は一つの文字しか残らない節を先に決めてから多く出る変数で分ける方法（分岐）で解いた。手間は、分ける方法が呼ばれた回数（分岐の数）で数えた。

問い：節の文字が二つか三つかで、何が変わるのか。

2. 満たせる割合の崖

計算 2.1：2-SAT を各 $200$ 問解き、満たせる割合を出した。

計算 2.2：3-SAT を各 $60$ 問解き、満たせる割合と分岐の数の中央値（かっこ内）を出した。

観察 2.3　崖の位置は、節の文字の数で大きく違う。2-SAT は $\alpha$ が $1$ から $1.5$ のあいだで崩れ、変数が増えるほど崖が鋭くなる。3-SAT は変数 $20$ 個で $\alpha=4.5$ に $0.583$、$5.0$ に $0.283$ と、$4$ を超えたところで崩れる。2-SAT を含意グラフで解いた $200$ 問と、3-SAT を分岐で解いた $100$ 問は、全部の割り当てを試した答えと一致した。

3. 崖の近くで解く手間

計算 3.1：同じ分岐の解き方で、崖の近く（3-SAT は $\alpha=4.25$、2-SAT は $\alpha=1.0$）の分岐の数を、変数の数を変えて各 $40$ 問で数えた。

観察 3.2　これが本稿の芯である。崖の近くで解く手間の伸び方が違う。変数を $20$ 個から $40$ 個に倍にすると、平均の分岐は 3-SAT で $3.377358$ 倍、2-SAT で $1.536885$ 倍になる。2-SAT は倍にするごとに $1.536885$・$1.693333$・$1.755906$ 倍で、変数を $8$ 倍にして $4.569672$ 倍と、変数に比例するより遅い。3-SAT は変数を $4$ 倍にして $7.347015$ 倍と、比例するより速い。

4. 分離子

観察 4.1　分離子は、満たせる割合を見るか、解くのに要る分岐の数を見るかである。満たせる割合だけを見れば、2-SAT にも 3-SAT にも崖がある。分岐の数を見ると、崖の上で手間が変数より速く伸びるのは節の文字が三つのときである。二つのときは、一つの文字を決めると残りが次々に決まり、分ける場面が少ない。

観察 4.2　論文348 の隣に置く。348 は、同じグラフで繋ぐのは安く、並べるのは高いことを示した。あちらは同じグラフの上の二つの問いで手間が分かれた。ここでは同じ形の論理式で、節の文字の数が二つか三つかだけで、崖の位置と手間の伸び方が分かれた。

観察 4.3　言わないこと。P と NP の関係も、変数を限りなく増やしたときの崖の位置も、よい解き方の比較も扱わない。示したのは、節の文字が二つか三つかで、崖の位置と崖の近くの手間の伸び方の両方が変わるということである。

5. 点呼と結び

1. 節の比 $\alpha=m/n$（第1節）：崖を測る横軸。
2. 二つの解き方は正しい（観察 2.3）：$200$ 問と $100$ 問。
3. 2-SAT の $\alpha=1.5$ で $0.695$ から $0.025$（計算 2.1）：崖が鋭くなる。
4. 2-SAT の $\alpha=1.0$ で $0.945$（計算 2.1）：変数 $320$ 個。
5. 3-SAT の $\alpha=5.0$ で $0.283$（計算 2.2）：崖はもっと右。
6. 3-SAT の分岐 $\mathbf{3.377358}$ 倍（観察 3.2）：本稿の芯。
7. 2-SAT の分岐 $\mathbf{1.536885}$ 倍（観察 3.2）：変数を倍にして。
8. 2-SAT は $8$ 倍で $4.569672$ 倍（観察 3.2）：比例より遅い。
9. 3-SAT は $4$ 倍で $7.347015$ 倍（観察 3.2）：比例より速い。
10. 満たせる割合か、分岐の数か（観察 4.1）：分離子・論文348。

結び：節が二つか三つかで、満たせるかどうかの崖の位置が変わり、崖の近くで解く手間の伸び方も変わる。2-SAT の満たせる割合は $\alpha$ が $1$ から $1.5$ のあいだで崩れ、$\alpha=1.5$ で変数 $20$ 個の $0.695$ から $320$ 個の $0.025$ へ落ちる。3-SAT は $4$ を超えたところで崩れる。節の文字が多いほど、一つの節を満たす道が多く、同じ数の節では崩れにくいからである。同じ分岐の解き方で変数を $20$ 個から $40$ 個に倍にすると、崖の近くの平均の分岐は 3-SAT で $3.377358$ 倍、2-SAT で $1.536885$ 倍になる。二つのときは一つを決めると残りが次々に決まるが、三つのときは分ける場面が残る。既刊との位置：論文348 の「同じグラフで繋ぐのは安く、並べるのは高い」の隣に、同じ形の論理式で節の文字の数だけが手間を分けることを置いた。正直に言えば、式は小さく、崖の極限の位置も、よい解き方での手間も述べていない。

参考文献

1. Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
2. Mézard, M., & Montanari, A. (2009). Information, Physics, and Computation. Oxford University Press.
3. 山岸勇輝 (2026). 『同じグラフで、繋ぐのは安く、並べるのは高い』[論文348]. YOI: https://www.yamagishiyuuki.com/yoi/348 ・ DOI: 10.5281/zenodo.22683555

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「節が二つか三つかで、満たせるかどうかの崖の位置が変わり、崖の近くで解く手間の伸び方も変わる」［論文874］. YOI: https://www.yamagishiyuuki.com/yoi/874

@misc{yamagishi2026yoi874,
  author = {Yamagishi, Yuuki},
  title = {Two or Three Literals per Clause Moves the Cliff of Satisfiability and Changes How the Work Near It Grows},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/874},
  note = {Preprint, edition 1}
}