# 計算複雑性 ## 定義 計算複雑性(computational complexity)とは、問題を解くのに必要な資源(主に時間、次いで記憶量)を入力サイズの関数として測り、問題そのものの難しさを分類する枠組みである。個々のアルゴリズムの実行時間を漸近記法で表す上向きの議論(上界)と、どんなアルゴリズムでもこれ以下にはできないという下向きの議論(下界)の 2 方向からなり、両者が一致したとき「そのアルゴリズムは漸近的に最適」と言える。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 3 関数の増加]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 8 線形時間ソート]]) 下界は問題に対してではなく計算モデルに対して立つ。比較ソートの $\Omega(n\lg n)$ は決定木モデルの帰結であり、キーが整数だという追加情報を使えば線形時間ソートが存在する。問題の難しさそれ自体を扱う枠組みが多項式時間帰着と NP 完全性であり、そこで難しいと分かった問題に対する現実的な妥協が近似アルゴリズムである。 ## 資源の測り方 - **漸近記法 $\Theta$・$O$・$\Omega$・$o$・$\omega$ は関数の集合として定義され、等式中では無名関数を意味する。** 定理 3.1 が $\Theta = O \cap \Omega$ を与える。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 3 関数の増加]] — 記法の定義と、指数 > 多項式 > 対数多項式という増加率の階層 - **入力サイズの定義は問題領域に依存し、同じ「$n$」でも意味が違う。** グラフでは頂点数と辺数の 2 つを取り、整数論的アルゴリズムでは値そのものではなくビット長 $\beta$ を取る。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 31 整数論的アルゴリズム]] — 算術演算回数とビット演算回数を二重に解析する - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 22 基本的グラフアルゴリズム]] — $\Theta(V+E)$ という 2 変数の表現 - **時間だけでなくアクセスの種類も資源になる。** B 木ではディスクアクセス回数と CPU 時間を分けて数え、前者を最小化するために分岐数を大きく取る。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 18 B木]] — DISK-READ / DISK-WRITE を単位コストとするモデル ## 下界とその回避 - **下界は計算モデルに対して立つのであり、問題に対して立つのではない。** 比較ソートの $\Omega(n\lg n)$ は決定木の葉が $n!$ 個必要という数え上げから従うが、比較以外の情報を使えばこの下界は適用されない。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 8 線形時間ソート]] — 定理 8.1 の下界と、計数ソート・基数ソート・バケツソートによる回避 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 20 van Emde Boas木]] — 優先度付きキューの $\Omega(\lg n)$ を整数キーの前提で $O(\lg\lg u)$ へ回避する同型の構図 - **上界と下界が一致したとき、そのアルゴリズムは漸近的に最適である。** ヒープソートとマージソートは系 8.2 により漸近的に最適な比較ソートである。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 6 ヒープソート]] / [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 8 線形時間ソート]] ## P・NP と帰着 - **多項式時間帰着 $\le_P$ は難しさを移送する道具であり、$L_1 \le_P L_2$ かつ $L_2 \in P$ ならば $L_1 \in P$ である(補題 34.3)。** 対偶を取れば、$L_1$ が難しいことから $L_2$ が難しいことが言える。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 34 NP完全性]] - **NP 完全性の証明は、既知の NP 完全問題からの帰着を 1 本示すことに還元される。** CIRCUIT-SAT を起点に SAT → 3-CNF-SAT → CLIQUE → VERTEX-COVER → HAM-CYCLE → TSP、および 3-CNF-SAT → SUBSET-SUM という連鎖が構成される。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 34 NP完全性]] — 図 34.13 の帰着木 - 関連: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 28 行列演算]] — 行列乗算と逆行列計算の漸近的等価性(定理 28.1・28.2)は、NP 完全性とは別の水準で同じ帰着の論法を使う - **NP 完全と判明した問題への現実的な対応が近似であり、その保証は階層をなす。** 定数近似(頂点被覆の 2 近似)・対数近似(集合被覆の調和数)・FPTAS(部分和問題)という 3 段階が第 35 章内で一望できる。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 35 近似アルゴリズム]] - 反証: 一般 TSP は $P \ne NP$ の下で定数近似が不可能であり(定理 35.3)、近似可能性は問題ごとに異なる ## 未解決の問い - 決定木モデルの下界は比較の回数を数えるが、実際の計算機ではキャッシュミスやディスクアクセスが支配的なことがある。B 木のディスクアクセスモデルのような「実機に近い計算モデル」に対する下界の理論はどこまで整備されているか。 - 近似可能性の階層(FPTAS・定数近似・対数近似・近似不可能)は、NP 完全性という一枚岩の内部に構造があることを示している。この構造を決める問題側の性質は何か。 - 整数論的アルゴリズムでビット長を入力サイズに取る流儀と、ソートで要素数を取る流儀は、擬多項式時間という概念を通じて接続する。この接続は本書内でどこまで明示されているか。 ## 未編纂の観察 - **最悪計算量と期待計算量の乖離は、同じデータ構造・同じアルゴリズムが繰り返し示す構図である。** クイックソートは最悪 $\Theta(n^2)$ だが期待 $\Theta(n\lg n)$、2 分探索木は最悪の高さ $\Theta(n)$ だがランダム構成なら期待 $O(\lg n)$、ハッシュ表は最悪 $\Theta(n)$ だが単純一様ハッシュの下で平均 $\Theta(1+\alpha)$ である。いずれも「悪い入力は存在するが稀である」という同一の状況にあり、乱択化(RANDOMIZED-QUICKSORT・universal hashing)または平衡化(2 色木)という 2 通りの処方箋が対置される。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 7 クイックソート]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 12 2分探索木]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 11 ハッシュ表]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 13 2色木]]) - **暗号の安全性は「解けない」ことではなく「多項式時間では解けないと信じられている」ことに依拠しており、計算複雑性の未解決問題が実用技術の前提になっている。** 第 31 章の RSA は大きな合成数の素因数分解が困難であることを安全性の根拠に置くが、その困難さは証明されていない。第 34 章が $P \ne NP$ を未解決としたまま NP 完全性の理論を構築しているのと同型に、実用系も未証明の仮定の上に立っている。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 31 整数論的アルゴリズム]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 34 NP完全性]]) - **乱択アルゴリズムは誤り確率を任意に小さくできるが、ゼロにはできないという別種の保証を導入する。** Miller-Rabin 素数判定は $s$ 回の反復で誤り率を高々 $2^{-s}$ に抑える(定理 31.39)。これは期待実行時間を保証する乱択化(クイックソート・SELECT)とは異なり、実行時間ではなく出力の正しさを確率的に保証するもので、Las Vegas 型と Monte Carlo 型という区別に対応する。本書はこの区別を用語として立てないが、第 7・9 章と第 31 章の間に事実として存在する。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 31 整数論的アルゴリズム]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 9 中央値と順序統計量]]) - **双対性は最適性の証明手段として、線形計画法と最大フローの両方に現れる。** 第 29 章の弱双対性は SIMPLEX が返す解が主問題・双対問題双方の最適解であることを示し、第 26 章の最大フロー最小切断定理は最大フローの値が最小切断の容量に等しいことを示す。第 29 章自身が後者を前者の具体例として参照しており、「上界と下界を別々に構成して一致を示す」という証明様式が、近似アルゴリズムの近似比証明(第 35 章)にも同じ形で受け継がれている。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 29 線形計画法]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 26 最大フロー]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 35 近似アルゴリズム]]) ## 関連 - 書籍: [[アルゴリズムイントロダクション 第3版]] - 概念: [[アルゴリズム設計技法]] / [[グラフアルゴリズム]] ## 出典 - T. コルメン, C. ライザーソン, R. リベスト, C. シュタイン 共著, 『アルゴリズムイントロダクション 第3版 総合版』, 近代科学社, 2013, 第 3・6・7・8・11・12・13・18・20・22・26・28・29・31・34・35 章.