計算爆発を抑え、非決定論を決定論に、確率論を決定論に還元する論理手法｜Finitization&Derandomization

サヴィッチの定理（NP→P）とアドレマンの定理（BPP→P）という2つのステップは確率論（運・ランダム）を決定論（構造・自動プログラム）へと100%完全に置き換える脱ランダム化（Derandomization）の証明形式のクリティカルパスである。

確率論を決定論へ置換する「2大論理ステップ」の構造

未来の市場や環境がもたらす不確実性を、100%確実な決定論へ変換するためには、以下の2つのフェーズ（ステップ）を順番に踏む必要があります 。

【ステップ1：空間による非決定性の回収】（サヴィッチの定理）

• 数理的役割： 未来の時間軸で指数関数的に大爆発（分岐）する「非決定性（無数の世界線）」を、消して書き直せる「有限の多項式空間（PSPACE）」に閉じ込めることで、決定性（普通の計算機）の手続きへと100%置換・シミュレートする（NPSPACE = PSPACE）。
• 経営上の意味： これから市場や競合が時間軸上で引き起こす「予測不能なあらゆる行動の分岐（NPSPACE）」を、あらかじめ制限された「境界空間（PSPACE：下界の固定）」の檻の中にすべて沈め込み、時間爆発を空間の制御へと置換するステップ 。
• Relationships Between Nondeterministic and Deterministic Tape Complexities

【ステップ2：構造による確率（ランダム）の除去】（アドレマンの定理）

• 数理的役割： サヴィッチの檻（PSPACE）の内部に生息する「確率的アルゴリズム（BPP 乱数）」は、アドレマンの行列（数え上げ論法）と増幅によって、すべてを網羅できるごく少数の『最良の証拠』のセットとして抽出でき、多項式サイズの決定論的な「ゲート回路（P/poly）」の中にエラー確率0%で完全に閉じ込められる 。
• 経営上の意味： 空間に閉じ込めた不確実性の内部にある「運や確率（ランダム）」を、人類の知性が舗装し終えた数学・言語というNamespace（厳選された最良の証拠のセット）という現実の回路へハードコードすることで、偶然を100%の必然（決定論的構造）へと還元するステップ。
• Two Theorems on Random Poly-nomial Time
• https://ieeexplore.ieee.org/document/4567965

確率論を決定論に置き換えるプロセスには、直列する2つの絶対的な論理ステップが存在する。

第一のステップは、未来の時間発展がもたらす非決定性分岐（NPSPACE）を、消して書き直せる『有界な空間』へ写像することで、決定性の檻の中にすべて回収するサヴィッチの定理（1970年）である。時間の爆発は、空間の制御へと置換される。

第二のステップは、その空間の内部に残された確率的ゆらぎ（BPP）を、増幅と数え上げによって、100%確実な決定論的構造（P/poly）へと決定的に変換するアドレマンの定理（1978年）である。

P/polyはPとは全く異なる広域クラスであり、RやREも突き抜けたrandomnesをP/polyは多項式時間で処理することができる。（Karp-Lipton Theorem）

Richard M. Karp, Richard J. Lipton

Some connections between non-uniform and uniform complexity classes

Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing (STOC '10),ACM Press (1980)

https://dl.acm.org/doi/epdf/10.1145/800141.804678

Turing machines that take advice(1982)

https://www.e-periodica.ch/digbib/view?pid=ens-001%3A1982%3A28%3A%3A331