2-SATとは何か｜二者間の禁止条件だけを多項式時間で監視する
2-SATとは、各節が2個以下のリテラルからなるCNF（Conjunctive Normal Form／連言標準形）の充足可能性問題である。Implication Graph（含意グラフ）と強連結成分（SCC／Strongly Connected Components）を用い、多項式時間で解ける。Pに属する。
3-SATや一般のCNF-SAT、3COL全体を2-SATへ還元できるわけではない。経営へ借りるなら、隣接する二者間の禁止条件・含意条件だけを二項射影として取り出し、局所Conflictを監視する手続である。全体問題を解いたことにはならない。
なお、一般化スーパーマリオブラザーズの到達が NP-hard であるという結果（Aloupis–Demaine–Guo–Viglietta, 2014/2015）は 3-SAT からの還元であり、2-SATの結果ではない。二項監視の多項式性と混同しない。
2-SATと3-SATの境界
| 問題 | 節幅 | 位置づけ |
|---|---|---|
| 2-SAT | 2以下 | P。Implication Graph + SCC |
| 3-SAT | ちょうど3 | NP完全 |
| 一般SAT | 制限なし | NP完全 |
2-SATでは、節 (a ∨ b) を (¬a → b) かつ (¬b → a) という含意に直し、グラフの到達関係から矛盾を検出する。同じ変数 x と ¬x が同一SCCに入ればUNSAT（Unsatisfiable／充足不能）である。
### 小さい例題
変数を x,y とし、節を (x ∨ y)、(¬x ∨ y)、(x ∨ ¬y) とする。含意辺を置くと y が真へ強制され、割当 x=0,y=1 または x=1,y=1 などで充足できる。一方、節に (¬x ∨ ¬y) を足して x と ¬x が同一SCCに入る構成へすると UNSAT になる。手で辺を追い、矛盾の有無を Yes/No で確認できる規模に留めることが要点である。
節に3リテラルが入ると、この手続だけでは一般に解けない。したがって「事業を2-SATにした」と言うときは、全体問題を解いたのではなく、監視可能な二項層を切り出したことを意味する。
バリューチェーンの二項射影
実務では、バリューチェーンの隣接ペアから禁止条件を書く。
| 接続 | 監視する問い |
|---|---|
| 論理 → 知財 | 公理が知財を防御できるか |
| 知財 → 企画 | 模倣困難な表現へ落ちているか |
| 企画 → 調達 | コンセプトが調達思想に準拠するか |
| 調達 → 製造 | 素材が品質を具現化するか |
| 製造 → 流通 | 経路が価値を保存するか |
| 流通 → 販売 | 検証可能な体験を届けるか |
目的は全体最適化ではない。局所Conflictを安く早く露出させることである。
3COLにおける二項層
3COLのCNFでは、頂点が少なくとも1色を持つ条件は3リテラル節になる。一方、同一頂点の排他や隣接同色禁止は二項節である。後者だけをImplication Graphで監視するのは、全体の多項式時間還元ではなく、二項射影の検査である。
局所検証の通過は、3COL全体の充足証明にはならない。サンプリング回数、許容誤差、停止条件は外部主体が固定する。
対話型の突き合わせ
独立に生成された二つの回答・証跡をVerifierが照合する設計は、2証明者対話の着想に近い。証明者間の通信を許さず、相関する問いへの回答が二項制約を破らないかを見る。
全部を解かずに局所矛盾を高確率で露出させることが目的である。通過は「たぶん正しい」ではなく、「いま抜いた局所については矛盾が見つからなかった」という記録である。
価格とシニョレッジ
需給に追随した値引きは、論理ゲートの整合性を壊すことがある。在庫過多を理由にHardな価格条件を崩すと、監視していた二項制約の意味が失われる。
2-SAT監視は、寛容な格子を保ちつつ、拒絶条件だけを数えるための道具である。ペルソナを細かく追うほど節が増え、監視コストが上がる。
チェックリスト
- 監視対象が二項制約に落ちているか
- 3リテラル以上の全体問題と混同していないか
- Implication GraphとSCCで矛盾を見ているか
- 局所通過を全体証明と書いていないか
- 値引きをHard破綻として扱えるか
2-SATの実務的価値は、難しい問題を簡単に見せることではない。多項式時間で監視できる層と、できない層を分け、前者だけで衝突を先に洗うことである。
Implication Graphの直感
節 (x ∨ y) は「xが偽ならyが真」「yが偽ならxが真」を同時に要求する。変数とその否定をノードにし、含意を有向辺で結ぶ。xから¬xへ、かつ¬xからxへ到達できるなら、xは真でも偽でも破綻する。
SCC圧縮後に同じ成分へxと¬xが入るかを見ればよい。この判定は多項式時間である。節幅が3になると、含意の局所構造だけでは足りず、一般には指数的な探索が残る。
アトリビューション解除
利用シーンを細かく切り分けるほど、変数と節が増える。「誰のどの瞬間か」を追いすぎると、2-SAT監視ではなく高幅のSATになる。実務では「邪魔にならない」水準へ抽象化し、二者間の禁止だけを残す。
ペルソナの放棄は無関心ではない。属性依存の過学習を捨て、構造的な寛容さを保つことである。
最高峰の手札と局所検証
出し惜しみをやめ、検証可能な体験を先に出す。市場のランダムな問いに対し、秘密を開示せず応答する。独立な二つの証跡を突き合わせ、二項制約の破れを探す。
全体最適の流通計画を2-SATで解いた、と書いてはならない。解けたのは監視層である。
監視ダッシュボードの最小構成
二者間エッジごとに、禁止条件、最終検証時刻、直近Conflict、担当Verifierを持つ。緑は局所通過、赤は矛盾、灰は未サンプリングである。全体の充足ゲージは置かない。置くと、局所通過を全体証明と誤読する。
週次で、赤の学習節をCDCL側へ渡し、再訪を防ぐ。灰が多い辺は、サンプリング予算を増やすか、辺の定義が粗すぎるかを見直す。
運用への落とし込み
バリューチェーン上の各辺について、禁止条件の文面、最終サンプリング日、Conflict回数、学習節への転送有無を表で持つ。週次レビューでは赤の辺だけを議題にし、緑の辺の成功談で時間を使わない。灰の辺が半数を超えたら、定義が粗いか予算不足かを決めて次週のBoundへ反映する。
価格条件をSoftへ落とした瞬間、監視の意味が薄れる。Hardへ戻すか、公理変更として版を上げる。Implication Graph上の矛盾は、担当者の印象ではなく辺の属性として保存する。月次で、矛盾密度の高い辺から製品・契約・導線のどれを直すかを一つ選ぶ。複数同時に直すと、どの学習節が効いたか分からなくなる。
まとめに代えて
2-SATは、難しい全体を簡単だと偽る道具ではない。多項式時間で監視できる二項の層を切り出し、Conflictを先に洗う道具である。3-SATや3COLの全体充足を主張したいなら、別の手続と別の証跡が要る。現場のダッシュボードが全体充足ゲージを見せ始めたら、設計が崩れている。赤と灰だけを追い、緑の局所通過を謙虚に記録する。価格の完全性を含むHardが、二項制約の意味を支える。値引きで整合性を買わない。
『P vs NP経営』の詳細はこちら https://link.amazon/B04IEdYsn