concensus vs conflict｜theory of computation
Theory of Computation、コンピュテーションに関する論理は、観測者、参加者が人間であり、機械であれ、自然であれ、情報処理資源が限定されている（computationally limited）ことが前提となっている。この前提公理は重要だ。あらゆる全知全能の神のような存在はいないというスタート地点が現実的なconflict（利益相反）の構造的観測とconsensus（合意形成）による無限演算循環の停止（演算の解）を導き出すのである。P vs NPは、演算資源が限定されたプレイヤーしかいないという前提のもと、解を再現する簡単なルートがあると仮定したときに推論が最適化されるというフレームワークである。（あるいは本当にP=NPが発見される可能性もある）
個人の最適化が全体の不利益を招いたり、論理的な手順が自身の首を絞めたりするような構造的矛盾は、文脈によっていくつかの呼び方があります。社会的ジレンマ（Social Dilemma）、調整の失敗（Coordination Failure）、非協力ゲームの非効率性は我々が地球で生きる上で前提公理になっている。
1. 個人の合理性と全体の合理性の乖離
「自分にとって一番得な行動」を選んだ結果、全員が損をする構造です。
- 合成の誤謬（Fallacy of Composition）
- ミクロの視点では正しい判断が、マクロ（全体）では最悪の結果を招くことを指します。
- ゲーム理論での呼称:「ナッシュ均衡の非効率性」
- 全員が「今の戦略を変えると自分が損をする」という安定状態（ナッシュ均衡）に達しているのに、その状態が全体で見ると非常に効率が悪い（Price of Anarchyが高い）状態です。
2. 共有資源の悲劇 (Tragedy of the Commons)
Price of Anarchy（無秩序の代償）や、リソースを奪い合う「食事する哲学者」の根底にある矛盾です。
- 構造: 誰もが自由に使える資源（道路、メモリ、共有の箸）があるとき、個々人が自分の利益を最大化しようとすると、資源が枯渇したり、渋滞・デッドロックが起きたりして、最終的に誰もその資源を使えなくなる矛盾です。
3. デッドロックと「循環参照」
「食事する哲学者」に代表される、論理的な手順そのものが生む矛盾です。
- 呼称:「循環待ち（Circular Wait）」
- AがBを待ち、BがCを待ち、CがAを待つ。個別のステップは「必要なものを待つ」という合理的な行動なのに、それが環（ループ）になった瞬間にシステム全体が停止します。
- これは自己参照的な矛盾の一種であり、ウィグダーソン教授が研究する「計算の複雑さ」の深淵（ゲーデルの不完全性定理など）にも通じる構造です。
なぜ「構造的矛盾」なのか
これらの問題が厄介なのは、「誰も間違った（不合理な）ことはしていない」のに、「結果が破綻している」という点にあります。むしろ、皆、正しいことをしていると信じ込んでいるところに全体の不都合が顕在化します。
- 悪意のある人がいなくても、渋滞は起きる（PoA）。
- 故障がなくても、システムは止まる（デッドロック）。
- 完璧な計算機でも、偏った乱数しか作れない（不完全なランダム性）。
こうした「個別の努力では解決できない構造的な矛盾」を、プロトコルの設計（数学的なルール記述）によって解消できるというのがToC(Theory of Computation)の基本思想です。
1. Randomness Extractors：不完全な現実から「完璧な盾」を作る
暗号の安全性は、多くの場合「予測不可能な乱数」に基づいています。しかし、現実世界のデバイス（キーボードの打鍵タイミング、熱ノイズなど）から得られる乱数は、統計的に偏りがあり「不純」です。
- 問題: 攻撃者が乱数の偏りを知っていると、暗号鍵を推測されるリスク（脆弱性）が生まれます。
- 解決策（抽出器の役割）: * 圧縮と凝縮: 1,000ビットの「質の低い乱数（不純な種）」を、数学的なフィルター（ハッシュ関数など）に通し、100ビットの「完璧に純粋な乱数」に変換します。
- シード（種）の活用: 非常に短い「完璧な乱数」を使って、大量の「不純なデータ」からランダム性を引き出します。
- 結果: これにより、デバイスの性能が不安定でも、数学的に「解読不可能な暗号鍵」を安定して生成できるようになります。
2. Price of Anarchy (PoA) の抑制：メカニズムデザイン
「各々が勝手に得をしようとすると、全体の効率が下がる」という問題に対し、理論家は「ルールそのものを書き換えて、エゴを公益に転換する」というアプローチを取ります。
- 「真実を言うのが一番得」にする設計:
- 例えば、クラウドコンピューティングのリソース割り当てで、各ユーザーが「本当はそれほど必要ないのに、多めにメモリを要求する」とシステムがパンクします。
- ここで、VCGメカニズムのような「自分が他人に与えた不利益（コスト）を自分で支払う」仕組みを導入すると、ユーザーは「正直に最小限の要求を出すこと」が自分の利益最大化に直結するようになります。
- 結果: 中央管理者が命令しなくても、個人の「欲」を利用してPoAを1（＝全体最適の状態）に近づけることができます。
解決策は、外部性にコストを課すことです。
- 混雑料金の導入: 交通渋滞の例では、混んでいる道を通るドライバーに「通行料」を課します。これにより、個人の「最短で行きたい」というインセンティブに「お金を払いたくない」という要素を加え、強制することなく交通量を分散させます。
- Vickrey-Clarke-Groves (VCG) オークション: 資源を割り当てる際、自分の希望を正直に言うことが最も得になるような報酬・課金体系を設計します。
解決策：スタックルベルグ・戦略（指導者の介入）
- 一部の誘導: 全体の10%の車両（例えば自動運転車やバス）だけを、全体の最適解に従って動かします。これだけで、残りの90%が勝手に動いたとしても、全体のPoAを劇的に下げられることが数学的に証明されています。
3. Dining Philosophersの理論的限界：デッドロック回避の境界線
これは並列コンピューティングやオペレーティングシステム（OS）における、「デッドロック（行き詰まり）」を説明するための古典的な思考実験です。
- 設定: 5人の哲学者が円卓に座り、食事と沈思黙考を繰り返しています。彼らの間には箸（またはフォーク）が1本ずつ、計5本置かれています。食事をするには左右2本の箸が必要です。
- 問題点: もし全員が一斉に「左の箸」を手に取ったらどうなるでしょうか？
- 全員が右の箸が開くのを待ちますが、右の箸は隣の人が左手で持っています。
- 誰も箸を離さず、誰も食事ができないまま餓死してしまいます。これがデッドロックです。
- 教訓: 限られたリソース（メモリ、ファイル、CPU）を複数のプロセスが奪い合う際に、いかにして「詰まり」を防ぎ、公平に割り当てるかという設計の重要性を説いています。
この問題の解決策（リソースの順序付けなど）はToC理論家がさらに踏み込むのは「どこまで条件を緩和しても安全か？」という限界の探求です。
- 分散システムの限界: * 「各プロセスが隣の状態しか見えない」という制約下で、かつ「一部のプロセスが故障する（箸を落としたまま動かない）」場合でも、全体が停止しないアルゴリズムは存在するか？
- ここで重要になるのが「待機なし（Wait-free）」という概念です。一人が止まっても他人が食事を続けられるための理論的な必要条件を数学的に証明します。
- 理論的境界: * 特定の条件下では「デッドロックを完全に防ぐアルゴリズムは存在しない」ことを証明することで、エンジニアが無駄な設計に時間を費やすのを防ぎ、代わりに「確率的な回避」などの現実的な妥協案へ導きます。
Worst case scenario
- 乱数抽出器: どんなに偏った（最悪な）データが来ても純粋な乱数を出す。
- PoA抑制: どんなに利己的な（最悪な）ユーザーが来てもシステムを最適に保つ。
- デッドロック回避: どんなに不運な（最悪な）タイミングでプロセスが動いても停止させない。
最悪の事態に対する数学的な保証をするのがToC理論の基本設計となります。