3-SATとは何か｜事業の制約を変数と節で構造化する
3-SATとは、各節がちょうど3個のリテラルからなる連言標準形（CNF）の充足可能性問題である。与えられた論理式を真にする真偽割当が存在するかを問う。NP完全問題の代表例であり、事業の制約を変数と節へ落とすときの基準形として使われる。
重要な区別がある。3-SATや3COL全体を2-SATへ還元できるわけではない。実務で使えるのは、隣接する二者間の禁止条件・含意条件だけを二項射影として取り出し、局所Conflictを監視することである。局所検証の通過は、問題全体の充足証明にはならない。
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）を調べれば、矛盾の有無が判定できる。一方、節に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で、どの条件がSoftか
- どの衝突を先に監視するか
ペルソナやデモグラフィックを完全に細かく追うより、構造として許容できる格子を設計し、拒絶される条件を数える方が、探索空間を制御しやすい。
バリューチェーンの二項射影
節幅を制限しない一般のCNF-SATや、3COL全体を2-SATへ還元できるわけではない。実務では、バリューチェーンから隣接する二者間の禁止条件・含意条件を抽出し、その二項射影だけを2-SATとして監視する。
| 接続 | 監視する問い |
|---|---|
| 論理 → 知財 | セキュリティ公理が知財を排他的に防御できるか |
| 知財 → 企画 | 独自知財が模倣困難な表現を導いているか |
| 企画 → 調達 | コンセプトが素材調達の思想に準拠しているか |
| 調達 → 製造 | 素材が品質を担保し、製造で具現化されているか |
| 製造 → 流通 | 経路が価値の保存則を維持しているか |
| 流通 → 販売 | 最終顧客に検証可能な体験を届けているか |
目的は全体最適化ではない。局所Conflictを安く早く露出させることである。
対話型の局所検証
最高峰の手札を市場へ提示し、顧客をVerifierとする対話を始める。市場からの予期せぬ問いに対し、秘密情報そのものを開示せず、検証可能なプロダクト体験と証跡を返す。
二証明者対話型証明の着想では、Verifierが相関する問いを二人のProverへランダムに送り、回答が制約を満たすか照合する。証明者間の通信をプロトコル中に許さない。実務では、独立に生成された二つの回答・証跡を突き合わせ、全部を解かずに局所矛盾を高確率で露出させる。
局所矛盾を検知した問い・回答ペアをConflictとして記録し、必要な範囲だけバックトラックする。サンプリング回数、許容誤差、採否、停止条件は外部主体が固定する。
やってはいけない混同
| 混同 | 正しい区別 |
|---|---|
| 局所検証の通過＝全体の充足 | 通過は局所整合の証拠に過ぎない |
| 3COL全体を2-SATへ還元した | 二項射影の検査であり、還元ではない |
| 衝突を増やせば精度が上がる | 衝突項の定義が曖昧だと探索が膨らむ |
| 値引きで需給を吸収する | 価格の完全性を壊すと論理ゲートが崩れる |
価格の完全性維持は、システムの統合性を担保するための演算規則として扱う。在庫過多などを理由とした値引きを、論理ゲートの破綻として排除できるかが問われる。
3-SATへ落とす手順の要約
事業を3-SAT型の照合へ落とすとき、次の順序が扱いやすい。
- 決定変数を0/1で列挙する
- Hardな禁止条件を節として書く
- Softな希望条件を重み付きで分ける
- 隣接する二者間の二項射影だけを2-SAT監視へ渡す
- サンプリングによる局所検証の回数と停止条件を外部主体が固定する
ここで得るのは、無限の最適化ではない。停止可能な検証手続である。全体を解かず、部分の衝突を先に見る。
実務チェックリスト
- 「なぜ欲しいか」ではなく「何が拒絶されるか」を数え上げているか
- 特定属性に依存しない、寛容な格子構造を維持しているか
- 利用シーンを細分化しすぎず、邪魔にならない水準へ抽象化しているか
- 値引きを論理ゲートの破綻として扱っているか
- 最高峰の手札を市場へ公開しているか
- 市場のランダムな要求に応える検証の場を用意しているか
- 秘密を明かさないまま正しい体験を返せているか
- バリューチェーンを二者間依存として監視しているか
3-SATは、すべてを解くための呪文ではない。事業の制約を変数と節へ落とし、全体問題と局所監視を分け、停止可能な検証手続を設計するための基準形である。
『P vs NP経営』の詳細はこちら https://link.amazon/B04IEdYsn