Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

論文874 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/874 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。

本文はサイトの記事でも読めます（2026年10月7日 15:20 に公開します）。

@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}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

節の長さが $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、含意グラフ、分岐、崖

Abstract

Whether a clause has $2$ or $3$ literals looks like a small difference.This paper measures the share of satisfiable random formulas and the work to solve them, and counts that the difference shows in two places: where the cliff lies and how the work grows.No new theorem or law is claimed.

First, both solvers are correct: $200$ 2-SAT problems solved with the implication graph and $100$ 3-SAT problems solved by branching agreed with trying all assignments (Section 2).

Second, the 2-SAT cliff sharpens between $\alpha=1$ and $1.5$: at $\alpha=1.5$ the share falls from $0.695$ with $20$ variables to $0.025$ with $320$, while at $\alpha=1.0$ it drops slowly: $0.975$, $0.960$, $0.945$ (Section 2).

Third, the 3-SAT cliff lies further right: with $20$ variables, the share is $0.850$ at $\alpha=4.0$, $0.650$ at $4.25$, $0.583$ at $4.5$ and $0.283$ at $5.0$ (Section 2).

Fourth, and this is the core. The work near the cliff grows differently: doubling the variables from $20$ to $40$ with the same branching solver multiplies the mean branches by $\mathbf{3.377358}$ for 3-SAT and by $\mathbf{1.536885}$ for 2-SAT (Section 3).

Fifth, 2-SAT work grows slower than the variables, 3-SAT faster: 2-SAT branches grow $4.569672$-fold for $8$ times the variables; 3-SAT grows $7.347015$-fold for $4$ times (Section 3).

Sixth, the separator is whether one looks at the share satisfiable or at the branches needed to solve: both have a cliff, but the work jumps on the cliff only when clauses have three literals (Section 4).

Keywords: satisfiability problem, 2-SAT, 3-SAT, implication graph, branching, cliff

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/874/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/874 はいつも最新の版を指します）。

YOI の一覧へ