カテゴリー: infinitude

確率は当てにするものではない。数学的証明を導くための随伴であり、探索センサーのようなものである。どんなに確率が高かったとしても100％が証明されていない以上は始めるべきではない。 NP=PCP(O (log n), O(…
Read more

PCP定理（Probabilistically Checkable Proofs Theorem）は、計算複雑性理論の一つで「巨大で複雑な証明も、ごく一部をランダムにチェックするだけで、その正しさを（高い確率で）判定でき…
Read more

1. 誕生の舞台：マンハッタン計画 (1940年代) 第二次世界大戦中、アメリカのロスアラモス国立研究所では、原子爆弾の開発（マンハッタン計画）が進められていました。 2. 命名：フォン・ノイマンの合流 ウラムはこのアイ…
Read more

計算論的観点：数学的構造とアルゴリズムの融合 従来の数学が「解の存在」を問うのに対し、計算論的観点は「その構造をいかに効率的に構成し、判定できるか」を問います。 1. 最適化（Optimization） 2. 不変式論（…
Read more

Lefschetz fixed-point theorem（レフシェッツの不動点定理）は、Solomon Lefschetz(1884-1972)によって一般化された不動点定理です。「空間の形（トポロジー）」と「その空間…
Read more

ブラウワーが「次元の不変性（Invariance of Dimension）」を証明したのは1911年のことです。 それまでの数学界では、カントールが「1次元の線と2次元の面は、点の数（濃度）としては同じである」ことを示…
Read more

アーサー・マーリン・プロトコル（Arthur-Merlin games）は、計算複雑性理論において「対話」と「乱数」の計算パワーを定義したモデルです。1985年にラズロ・ババイ（László Babai）によって提唱され…
Read more

P = BPP とは、「計算において『乱数』はブーストにならない（＝乱数を使って解ける問題は、すべて乱数なしでも効率的に解ける）」という数学的な予想です。 1. 言葉の定義 2. なぜ P = BPP と考えられているの…
Read more

I am proving pure mathematical tractability by distinguishing cardinality of randomness in worst-case scenario…
Read more

Circuit Complexity（回路計算量）とは、計算理論の一分野で、ある計算問題を解くために必要な「論理回路」のサイズや深さを研究する学問です。 通常の計算量理論（PやNPなど）が「プログラムの実行時間やメモリ使…
Read more