計算量理論と 暗号 今回のテーマ は計算量理論に 関する も のです． 計算量と は， 要する に “問題の難し さ ” のこ と ですが， 数 学で “こ の定理の証明は難し い ” と 言う と き の “難し さ ” と は違い， “やれば必ずいつかでき る こ と は分かっ て いる が， 面倒だ ” と いう 意味の作業量のこ と です． ただし “いつか ” に は “数十億年後” も 含ま れま す． こ こ で， 問題が必ずいつかは解け る ， と いう のはこ の問題の答を 与え る 処方， すな わち 有限ス テッ プで 終わる よ う な 解法のア ルゴリ ズム が知ら れて いる と いう こ と です． 解き 方に は， 良いも の (効率的な も の ) と 悪いも の (非効率な も の ) があり ま すので， 答を 得る のに ど れく ら いの時間がかかる かは， ア ルゴリ ズム を 指定し た と き の話です． た だし ， 問題自身の難し さ を 言う 場合は， 現在知ら れて いる 最良のア ルゴ リ ズ ム でど のく ら いかかる かと いう 意味ですが， 将来も っ と 良いア ルゴリ ズム が発見さ れる かも し れな いので， こ ち ら に ついて は “取り 敢え ず” の主張です． こ れを 恒久的な 主張に する に は， “こ の問題に はこ れ以上効 率の良いアルゴリ ズム は存在し な い ” と いう こ と の証明が必要ですが， こ れは一般に超難問で， 多く の場合 未解決です． 計算量は普通， コ ン ピュ ータ を 使っ て 解いたと き にかかる 時間と 解釈さ れ， 計算時間と も 呼ばれま す． し かし コ ン ピュ ータ の速さ はま ち ま ち で， 将来も っ と 速いコ ン ピュ ータ ができ る かも し れな いので， 計算にか かる 実時間に は理論的な 意味はあり ま せん． (実用的に は重要ですが .) そ れでこ れを 理論化する に は， 一つ の固定し た問題ではな く ， サイ ズ n でパラ メ ータ 付け さ れた 問題のク ラ ス を 対象と し ， n → ∞ と し たと き こ れを 解く のに 必要な 計算時間が n のど んな 関数で増え て ゆく かで判定し ま す． こ のために は整数論や 微分方程式な ど ， 純粋数学でも お馴染みのラ ン ダウ の記号 O(g(n)) が使われま す． 例え ば， 例 1. ソ ート の問題 与え ら れた n 個の数を 大き さ の順に 並べ替え る のに 要する 時間は， 最良のア ルゴリ ズム で O(n log n). 例 2. 行列式の計算 与え ら れた n 次正方行列の行列式を 計算する のに 要する 時間は， こ の行列が特殊な 形を し て いる のでな け れば O(n3 ). 1/3 2/3 例 3. 因数分解 n 桁の整数の素因子を 求める に は， 現在最良のアルゴリ ズム で O(ecn (log n) ) の時間が かかる ． こ れは ∀k に ついて O(nk ) (多項式) よ り は大き いが， O(ecn ) (指数函数) よ り は小さ い． 最後に出て き た “ ∃k について O(nk ) ” が， 多項式時間計算量と 呼ばれ， 話の主役と な る も のの一つです． こ のよ う に 計算量を 漸近理論と し て 捉え る こ と に よ り ， コ ン ピ ュ ータ の速さ の違いは単に 定数因子の違い と な り ， 計算量と いう も のが環境に 依ら な い意味を 持っ て ， 数学の対象と な る のです． 計算量理論は， 大き く 分け て 次の二つの全く 正反対の意味で実世界と 深く 関わっ て いま す ： ア ルゴリ ズムの効率化 頻繁に解く 必要がある 問題について ， 既に有る 解法よ り はも っ と 高速な も のは無い ✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿ か？ と いう のが， 組合せ論， 計算幾何学， グラ フ 理論の実用的な 問題で屡々 話題と な り ま す． 例 1 のソ ート の問題は， 子供に やら せて も 多分バブルソ ート と 呼ばれる O(n2 ) の解法に 近いも のを 自分で見つけ 出すで し ょ う ． こ れを 上述の O(n log n) で解く には， 大学で情報系の学科に入る と 1 年生で教え ら れる 有名な ソ ー ト アルゴリ ズム が必要にな り ま す． 線形計画法と いう 工学の重要な ツ ールでは， 1980 年代に Karmarkar が 新し い高速解法を 発見し ， ア メ リ カ で特許を 取っ た た め熱い議論が起き ま し た ． 良い解法はお金儲け に な る かも し れま せん． 絶対に速く は計算でき ないこ と の保証が欲し い こ んな こ と に実用的な 意味が有る のか不思議に思われる か ✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿ も し れま せんが， 現在イ ン タ ーネ ッ ト を 支え て いる セ キ ュ リ ティ 基盤は， 因数分解が速く はでき な いこ と を 信じ て 作ら れた RSA 暗号と いう 公開鍵暗号に 依拠し て いま す． こ れは信じ ら れて いる だけ で， も し 因数 分解が多項式時間ではでき な いこ と を あ な た が証明でき た ら ， 有名な 懸賞問題の一つを 解いたこ と に な り ， 100 万ド ルが手に入り ま す． 逆に， 多項式時間の因数分解アルゴリ ズム を 発見し て し ま っ たら ， 世の中は大 混乱に 陥り ， お金が儲かる かど う かは分かり ま せんが， あな たは間違いな く “時の人” に な れる でし ょ う ． こ の講義では， 計算量のこ れら 二つの面に ついて ， いろ んな 分野に 渡る 有名な 実例を 交え な がら ， な る べく 初等的に ， し かし 単な る お話よ り は内容の有る 紹介を し て ゆき た いと 思いま す．
© Copyright 2024 ExpyDoc
