3-SATとは何か｜事業の制約を変数と節で構造化する
3-SATとは、各節がちょうど3個のリテラルからなる連言標準形（CNF／Conjunctive Normal Form）の充足可能性問題である。与えられた論理式を真にする真偽割当が存在するかを問う。CNFは「節（OR）の連言（AND）」の形である。NP完全問題の代表例であり、事業の制約を変数と節へ落とすときの基準形として使われる。
Stephen A. Cook（スティーブン・A・クック、1939–）と Leonid A. Levin（レオニード・A・レヴィン、1948–）に始まるNP完全性の系譜のうえで、3-SATは Karp の21問題をはじめとする還元の基準形として使われる。
ゲーム到達の難度の例として、Greg Aloupis（グレッグ・アルーピス）、Erik D. Demaine（エリック・D・デメイン、1981–）、Alan Guo（アラン・グオ）、Giovanni Viglietta（ジョヴァンニ・ヴィリエッタ）による “Classic Nintendo Games are (Computationally) Hard”（FUN 2014／TCS 2015）は、一般化したスーパーマリオブラザーズの到達が NP-hard であることを、3-SAT からの還元で示した。3-SATと3COLは変換可能である。
SAT、2-SAT、3-SATの違い
SAT（Boolean Satisfiability Problem／ブール充足可能性問題）は、変数への0/1割当によって、すべての節を真にできるかを問う問題である。
| 問題 | 節の形 | 計算量の位置づけ |
|---|---|---|
| 2-SAT | 各節が2リテラル以下 | Pに属する。Implication GraphとSCCで解ける |
| 3-SAT | 各節がちょうど3リテラル | NP完全 |
| 一般CNF-SAT | 節幅に制限なし | NP完全。3-SATへ多項式時間還元可能 |
2-SATは多項式時間で解ける。Implication Graph（含意グラフ：節を含意辺へ直し、変数とその否定を結ぶ有向グラフ）を作り、強連結成分（SCC／Strongly Connected Components：互いに到達可能な頂点のまとまり）を調べれば、矛盾の有無が判定できる。一方、節に3個のリテラルが入ると、一般には同じ手続では解けない。
3-SATがNP完全であるとは、NPに属するすべての問題を多項式時間で3-SATへ変換できること、かつ3-SAT自身がNPに属することを意味する。もし3-SATに多項式時間アルゴリズムが見つかれば、P＝NPが成立する。
3COLとの関係
3COL（3彩色可能性）は、各頂点へ3色のいずれか一つを割り当て、隣接頂点を異なる色にできるかを問うNP完全問題である。
検証の骨格は次のとおりである。
- 各頂点 v と色 c∈{1,2,3} にブール変数 x(v,c) を置く
- 各頂点が少なくとも1色を持つ条件を (x(v,1) ∨ x(v,2) ∨ x(v,3)) と書く
- 同じ頂点が2色を同時に持たない条件を、色ペアごとに二項節で書く
- 各隣接辺と各色について、同色を禁止する二項節を置く
Step 2に3リテラル節があるため、式全体は2-SATではない。一方、頂点内の排他制約と隣接同色禁止は二項節なので、局所的な2-SAT層としてImplication GraphとSCCによる矛盾監視に使える。これは全体問題の多項式時間還元ではなく、二項射影の検査である。
なぜ事業に変数と節が必要か
事業の制約は、文章のままでは衝突を数えにくい。「欲しい理由」を増やすほど過学習に近づく。管理すべきは、顧客が離脱する「欲しくない理由」、すなわち衝突項の数え上げである。
変数と節に落とすと、次が明示される。
- 何を0/1で決めるか
- 何と何が同時に成立してはいけないか
- どの条件がHardで、どの条件がEasyか
- どの衝突を先に監視するか
コンピュテーションの観点からセールス＆マーケティングを再定義するのであれば、状態空間が爆発するペルソナやデモグラフィックを完全に細かく追うより、購買条件の充足問題として、格子を設計し、拒絶される条件を数える方が、探索空間を制御しやすい。
バリューチェーンの二項射影
節幅を制限しない一般のCNF-SATや、3COL全体を2-SATへ還元できるわけではない。経営へ応用するなら、バリューチェーンから隣接する二者間の禁止条件・含意条件を抽出し、その二項射影だけを2-SATとして監視する手続である。全体の多項式時間還元を主張するものではない。
| 接続 | 監視する問い |
|---|---|
| 論理 → 知財 | セキュリティ公理が知財を排他的に防御できるか |
| 知財 → 企画 | 独自知財が模倣困難な表現を導いているか |
| 企画 → 調達 | コンセプトが素材調達の思想に準拠しているか |
| 調達 → 製造 | 素材が品質を担保し、製造で具現化されているか |
| 製造 → 流通 | 経路が価値の保存則を維持しているか |
| 流通 → 販売 | 最終顧客に検証可能な体験を届けているか |
目的は全体最適化ではない。局所Conflictを安く早く露出させることである。
対話型の局所検証
最高峰の手札を市場へ提示し、顧客をVerifierとする対話を始める。市場からの予期せぬ問いに対し、秘密情報そのものを開示せず、検証可能なプロダクト体験と証跡を返す。
二証明者対話型証明の着想では、Verifierが相関する問いを二人のProverへランダムに送り、回答が制約を満たすか照合する。証明者間の通信をプロトコル中に許さない。実務では、独立に生成された二つの回答・証跡を突き合わせ、全部を解かずに局所矛盾を高確率で露出させる。
局所矛盾を検知した問い・回答ペアをConflictとして記録し、必要な範囲だけバックトラックする。サンプリング回数、許容誤差、採否、停止条件は外部主体が固定する。
定義の整理
| 混同 | 正しい区別 |
|---|---|
| 局所検証の通過≠全体の充足 | 通過は局所整合の証拠に過ぎない |
| 3COL≠2-SAT | 二項射影の検査であり、還元ではない |
| 衝突≠精度 | 衝突項の定義が曖昧だと探索が膨らむ |
| 値引≠需給工場 | 伝統的経済学の需給曲線はコンピュテーションでは成立していない。限界利益率の最大化問題 |
3-SATへ落とす手順の要約
事業を3-SAT型の照合へ落とすとき、次の順序が扱いやすい。
- 決定変数を0/1で列挙する
- Hardな禁止条件を節として書く
- 充足条件を重み付きで分ける
- 隣接する二者間の二項射影だけを2-SAT監視へ渡す
- サンプリングによる局所検証の回数と停止条件を外部主体が固定する
目的とするのは無限の最適化ではなく、停止可能な検証手続の有限解である。全体を解かず、部分の衝突を先に見る。
実務チェックリスト
- 「なぜ欲しいか」ではなく「何が拒絶されるか」を数え上げているか
- 特定属性に依存しない、寛容な格子構造を維持しているか（言語非依存）
- 利用シーンを細分化しすぎず、邪魔にならない水準へ抽象化しているか
- 値引きを論理ゲートの破綻として扱っているか（Aかつ¬Aの論理矛盾、論理爆発）
- 手札を市場へ公開しているか（公開コインゲーム）
- 市場のランダムな要求に応える検証の場を用意しているか（hardness vs randomness, randomness vs pseudo-randomness)
- 秘密を明かさないまま正しい体験を返せているか（ゼロナレッジプルーフ）
- バリューチェーンを二者間依存として監視しているか
3-SATは、すべてを解くための万能ツールではないものの、NP-hardから、NP以下の問題を特定し、有限手続きに落とすための次元切り捨ての満足解導出手法として、事業の制約を変数と節へ落とし、全体問題と局所監視を分け、停止可能な検証手続を設計するための基準型である。
『P vs NP経営』の詳細はこちら https://link.amazon/B04IEdYsn