カテゴリー: randomness

ワーストシナリオケースを３回くらい検証すればどんな事業でも大体弱点がわかってしまう仕組みが経験的にある。 複雑に見えるシステムでも、少数の極端な条件（最悪ケース）をテストするだけでバグの大部分を網羅できるという現象は理論…
Read more

事業=チューリングマシンとしたNP-complete一般化 コンシューマーブランドにおける一般化 1. ブランドアイデンティティの公理宣言とパラドックス 真に普及するブランドは、自らその正当性を証明しようとすると、自己言…
Read more

立体は4色以上で塗り分け可能である。一方平面は1-4色で塗り分け可能である。3 colorableの判定はNP completeであるものの、現代のコンピューターはNP completeを3-SATに変換してCDCL(c…
Read more

情報を開示しても秘匿しても証明能力の上限に違いは生まれない。 1. 情報の開示と秘匿による証明能力の等価性 AM, Arthur-Merlin game or User-Expert game 検証者（アーサー）が用いる…
Read more

Theory of computationを日本語訳したいのだが、日本語にしてしまうと射像がたりず、意味が失われてしまう単語をどう表現すべきなのか。真のComputationは決定性、非決定性を扱うコミュニティである。コ…
Read more

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

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

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

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

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