latest update: 2022.05.30
2022.05.30 空間計算量をなぜあまり考えないのかの理由の説明が間違っていたので修正しました
- 力任せ探索
- 判定・探索・最適化
- 計算量
- ビッグオー記法
- P
- NPとco-NP
- 効率的に解ける問題
- NP困難，NP完全
- P≠NP問題
- 計算困難問題へのアプローチ
- 設計思想の紹介
- まとめと振り返り
- Appendix 補足
力任せ探索
卵の問題
さて，突然ですが問題*1です．
卵がもったいないやろという感じですが，ちょっとまじめに考えてみてください．
まず思いつくのは，１階から $T$ 階まで順番に試していったらどうか？ということです．これは実際に正しい答えになっています．$T$ 階まで試してなお割れなければ，卵は最上階から落としても割れないということが分かりますし，そうでなければ卵が最初に割れた階のひとつ下がギリギリであるということになります．
しかしこの方法をとった場合，最悪の場合 $T$ 回試さなくてはなりません．テスト用の卵は潤沢にあるといってもテストの回数分だけ大事な卵がわやになるわけですから，できるだけ試行の回数は減らしたいものです．もっと少ない試行回数で判定できる方法はないものか？という疑問が自然と湧いてきます．
力任せ探索より効率的に
実のところ，非常に大雑把な言い方を許せばですが，この種の疑問こそ離散最適化（組合わせ最適化ともいいます）という分野の出発点といえるものです．離散最適化ではその名の通り，離散的な集合から条件を満たすものを探してくるような問題を扱うのですが，そういった問題が連続的な問題と異なる特徴的な点のひとつがいま述べた卵の問題に現れています．つまり，探すべき解の候補がそもそも有限個しかないということです．ですからしらみつぶしに全ての可能性をあたってしまえば，解は見つかります．この「すべての可能性を確かめる」という頭の悪いアルゴリズムのことを，力任せ探索と呼びます．上記の卵の問題では，「１階から $T$ 階まで順番に試してみる」というアルゴリズムが力任せ探索にあたります．
力任せ探索をすればとりあえず解けるということは，解けるだけでは十分ではないということです．代わって，どれだけ少ない労力で解けるか？ということが重要性を増してきます．力任せ探索は芸のない自明（あたりまえ）なアルゴリズムなので，とりあえずこれを超えることを目標にするのが自然でしょう．
すなわち，次のような動機を得たことになります．
文章の意味があいまいに感じられると思いますが，それは意図的なもので，後から詳細を補っていくつもりです．とにかく，この疑問は離散最適化において中心的な位置を占めていると言っても過言ではないものです．これから，この疑問の帰結についてお話することになりますので記憶にとどめておいてください．
二分探索
卵の問題に戻りましょう．この問題で力任せ探索より効率的な解き方があるか？という問題が未解決でした．先回りして答えを言ってしまうと「できる」のいうのが答えです．この答えに現れる考え方はこの後もたまに遭遇する重要なものですので，ここで詳しく解説します．
まず最初に $c$ 階から落としてみたとします．その結果卵が割れれば，知りたい値 $F$ は $c$ より小さいことが分かります．$F$ 階から落としても割れないはずだからです．また，$c$ 階から落とした卵が割れなかったとすると，知りたい値 $F$ は $c$ 以上であることが分かります．まとめると，この一回の試行で探す範囲を 「１以上 $c -1 $ 以下の区間」または「$c$ 以上 $T$ 以下の区間」に絞り込むことができます．それぞれの区間のサイズは $c-1$, $T - c +1$ ですので，最悪の場合でもできるだけ探す範囲を絞り込もうとすると，$c = T / 2$ とするのがよいことが分かります．このとき，探索すべき範囲は $T$ から半分の $T/2$ になります．
実際には $c$ は整数でなければならないわけですが， $c = \lfloor T/2 \rfloor$ などとすれば問題ありません．なお記号 $\lfloor x \rfloor$ は $x$ 以下の最大の整数を返す関数です．
同じことがすべてのステップで言えます．うまく $c$ を選べば，探索すべき範囲を半分以下にすることができるのです．したがって，上記のように各ステップで巧妙に $c$ を選び続けることによって，卵を落とす回数を $\log_2 T$ 回以下に改善することができます．力任せ探索の場合は $T$ 回の試行が必要だったので，劇的に改善できたことになります．たとえば $T = 60000$ のとき，力任せ探索なら６万回の試行が必要ですが，上記の工夫されたアルゴリズムの場合はたったの16回で済むことになります．
このように，ステップごとに探す範囲を半分以下にするテクニックを二分探索と言います．
判定・探索・最適化
今まで離散最適化で取り扱う問題がどのようなものであるかについて「離散的な問題」程度の説明しかしてきませんでしたが，これ以降もう少しきちんとした説明をしていこうと思います．*2
バーの喧嘩抑制問題
さて，再び唐突ですが次の問題*3を考えてみてください．
「喧嘩が発生するのはそのひとたちの相性のせいであって，それ以外の原因はない」と仮定できるケースはそんなにないかもしれませんが，それほど非現実的な仮定でもなかろうと思います．今回は解かなくてもよいです．問題設定に慣れていただければ十分です．
グラフ理論
余計な情報を削ぎ落し，問題を考えやすくするためにいくつか言葉を用意しておきましょう．
まず，グラフ（graph）というものを定義します．グラフとは，直観的には「頂点と，その間をつなぐ辺の組」のことです．辺に対して向きを考える場合と考えない場合があり，考える場合は有向グラフ，考えない場合は無向グラフといいます．頂点集合が $V$ で，辺の集合が $E$ であるようなグラフ $G$ のことを，単純に $G = (V,E)$ と書きます．絵を描くとすれば……こんな感じのやつです．
たとえば鉄道路線図や友人関係は，無向グラフの例になっています．また緊急時用の電話連絡網は，有向グラフの例になっています．
頂点 $v$ と $w$ の間に複数の辺（並列辺）があることを許すこともありますが，このブログでは特に断らない限り並列辺はないものとします．つまりグラフは単純であると仮定します．また，辺の両端点が同じ点になること（自己ループ）を許すこともありますが，このブログではやはり特に断らない限り自己ループはないものとします．
以上の準備のもとで，さきほど述べたバーの喧嘩抑制問題をグラフの言葉で書き直してみましょう．舞台がバーであるとか，防ぎたいことが喧嘩であるとかいった個別の問題に依存する情報を落として，シンプルにすることができます．
まず，$n$ 人の常連の集合を頂点集合 $V$ としましょう．$|V| = n$ です．そして頂点 $v$ と $w$ の間には，$v$ が表すひとと $w$ が表すひとが喧嘩をする可能性があるときに（そしてその時に限り！）辺を張ることにして，辺の集合を $E $ とします．$|E| = m$ です．
このようにすると，「喧嘩が全く起こらないように出禁にするひとたちを決める」というのは，頂点の部分集合 $S \subseteq V$ であって，すべての辺 $e \in E$ に対して $e$ の両端点のいずれかが $S$ に属するような，そんな $S$ を求めることに帰着されます．そういう $S$ のことを頂点被覆または点カバーといいます．
たとえば，次の無向グラフでは赤い点の集合が頂点被覆になっています．
問題では「できるだけ出禁にするひとを少なくしたい」ということでしたが，これはサイズが最小の頂点被覆を求めることに対応します．まとめると，バーの喧嘩抑制問題は次の離散グラフにおける問題に帰着されることがわかりました．
要求：頂点被覆 $S \subseteq V$ であって，サイズ $|S|$ が最小のものを求めよ．
記述が大幅に短くなってスッキリしましたね．
判定問題の重要性
さて，離散グラフの言葉によるモデル化で得られた頂点被覆問題ですが，どのようにモデル化するかについて意味のよく似た異なる形式が３つあります．
１つめは，判定問題としての定式化です．判定問題というのは，YESかNOかで答えられる問題のことです．頂点被覆問題の場合は，解のサイズをパラメータとして独立させて，「このサイズ以下の解はあるか？」という問題にすれば自然に判定問題とみなすことができます．つまり，以下のようにするわけです．
パラメータ：解のサイズ $k$
要求：頂点被覆 $S \subseteq V$ であって，サイズ $|S|$ が $k$ 以下のものは存在するか？
２つめは，探索問題としての定式化です．YESかNOだけではなく，YESのときには具体的に解を返すことを要求するものです．頂点被覆問題の場合は以下のようになります．
パラメータ：解のサイズ $k$
要求：頂点被覆 $S \subseteq V$ であって，サイズ $|S|$ が $k$ 以下のものは存在するか？存在するならば具体的に構成しなさい．
３つめは，最適化問題としての定式化です．これは目的関数を最大化あるいは最小化するようなものをひとつ具体的に返しなさいというものです．「離散最適化」という名前の通り，だいたいの問題は自然に最適化問題として定式化することができます．さっきと同じですが再掲しておきます．
要求：頂点被覆 $S \subseteq V$ であって，サイズ $|S|$ が最小のものを求めよ．
以上の３通り，どれも自然な定式化であると感じられるのではないでしょうか．どれを選ぶのか悩ましいですね．
離散最適化というくらいなので最適化問題を主に考えたいところですが，実は理論的には判定問題が最も扱いやすいので今後だいじなところでは判定問題を考えることが多くなります．理由は，かつてえらいひとたちが決めたことですので私のような若輩には推測することしかできないのですが，「出力のサイズがYESかNOかの１ビットで固定されるのが嬉しいから」というのはあると思います．
考える対象を判定問題に限定してしまって大丈夫なのか？という心配がありそうですが，大丈夫です．なぜかというと，ほかの２つのタイプの問題は判定問題に変形することができて，その変形後の判定問題が解けると元の問題についても十分な知見が得られることが多いからです．つまり，帰着ができるわけです．ですから今後，私が理論的な話をするときに考察範囲を判定問題に限定していても怒らないでくださいね．
自己リダクション
「判定問題だけ考えれば十分だって？すぐには見えてこないな……」と思われた方へ．大丈夫です．そんなこと突然言われたら納得いかなくて当然です．私の前節での説明が不十分だっただけです．
帰着の仕方を，これから詳しく説明しようと思います．一般的に説明するには準備が足りないので，具体例をいじることしかできないのですが，それでも雰囲気はつかんでいただけるかと思います．
探索問題への帰着
まず，最適化問題の代わりに探索問題を考えれば十分であることを示しましょう．これは，先ほど卵の問題を例にとって説明した二分探索を使用することでわかります．再び頂点被覆問題を例にとりましょうか．探索問題を解いてくれるサブルーチンが与えられていて，次の問題を解きたいものとします．
要求：頂点被覆 $S \subseteq V$ であって，サイズ $|S|$ が最小のものを求めよ．
このとき解のサイズ $|S|$ は，０以上であり，頂点全体のサイズ $|V|$ を超えることもありません．つまり $n = |V|$ とするなら $0 \leq |S| \leq n$ であるわけです．したがってこの区間に対して解のサイズ $k$ に関する二分探索を行えば，最悪の場合でも約 $\log_2 n$ 回で最小サイズの頂点被覆を求めることができます．
探索問題が判定問題より難しいことは明らかなので，これで探索問題を考えれば十分であることがわかりました．
判定問題への帰着
では，探索問題の代わりに判定問題を考えれば十分であることはどうしたら示せるでしょうか．少しだけ複雑になりますが，これも一般的な方法があって，可能です．
判定問題を解くサブルーチン $A$ が与えられているとします．$A$ は，入力グラフ $G$ とパラメータ $k$ を入れるとYESかNOかの答えを１ステップで返してくれるおりこうな機械です．このときに，以下の探索問題を解きたいものとします．
パラメータ：解のサイズ $k$
要求：頂点被覆 $S \subseteq V$ であって，サイズ $|S|$ が $k$ 以下のものは存在するか？存在するならば具体的に構成しなさい．
どうすればいいでしょうか？どうやったら解の存在だけから解そのものを復元できるでしょうか？ポイントは，便利な機械 $A$ を使って入力グラフに前処理を行い，入力サイズを小さくすることができる，ということです．入力サイズを再帰的に小さくしていくことで，解の構成という厄介な仕事をやりおおせることができます．
具体的に考えていきましょう．頂点 $v$ を選んで，グラフ $G$ から点 $v$ を除いたグラフ $G - v$ を考えます．これに対してサブルーチン $A$ を適用したら何が得られるかについて考えてみましょう．実は次のことがいえます．
注意：本来なら $G - v$ ではなく $G \setminus \{ v \}$ と書くべきなのですが，面倒なので $G - v$ と書いています．同様の理由で，$S \cup \{ v \}$ のことも $S + v$ と書いたりします．
（１）$G$ のサイズ $k$ 以下の頂点被覆 $S$ であって，点 $v$ を含むものがある．
（２）$A(G - v , k-1) = \mathrm{YES}$.
(1) から (2) をまず示す．条件を満たす $S \subseteq V$ が与えられたとする．このとき $S - v$ は $G -v$ の頂点被覆になっていて，しかも $|S - v| = |S| - 1 \leq k - 1$ である．したがって $A(G - v , k-1) = \mathrm{YES}$ が成り立つ．
(2) から (1) を示そう．$G - v$ におけるサイズ $k-1$ 以下の頂点被覆 $S$ が与えられたとする．このとき $ S + v$ は $G$ の頂点被覆であって，$v$ を含むものになっている．しかも $|S + v| \leq |S| + 1 \leq k$ なので，サイズも $k$ 以下である．
この補題により，$A(G-v,k-1)$ がYESならば $v$ を含む（サイズが $k$ 以下の）頂点被覆が存在することがわかります．さらに $A(G-v,k-1)$ がNOであったときには，どんな（サイズが $k$ 以下の）頂点被覆も $v$ は含まないわけですから，代わりに $v$ に隣接する頂点集合 $N(v)$ の元は含まれているはずだ……ということがわかります．
こうして解になりえるかどうかが決定された頂点は除外していくことにより，入力のサイズを順次小さくしていくことができ，帰着が可能になります．これでほかの２つのタイプの定式化が判定問題に帰着できることがわかりましたね．
ただし，先述の疑問であるこれですが，
これの「こうした離散的な問題」のところを判定問題に置き換えられるほど常に綺麗に帰着できるわけではないので，そこんところもご承知おきください．
なおこのように，「判定問題ver.が解ければ最適化ver.も簡単に解くことができる」という性質を満たす最適化問題のことを，自己リダクション可能というようです．*4 今回は頂点被覆問題という問題を例にとって示しましたが，たいていの問題は同様の方法が使えて，自己リダクション可能であることが示せることが知られています．
計算量
さて，先述の疑問には曖昧な部分がありましたね．
いろいろありますが，まず「本質的に効率的」というのをどうやって定義するかを問題にしましょう．アルゴリズム同士の効率性を比較する尺度を導入したいわけです．
一般に使われるのは，時間計算量と空間計算量です．
時間計算量というのは，アルゴリズムが終了するまでのステップ数のことです．より正確には，アルゴリズム $A$ の計算時間が高々 $g(n)$ であるとは，サイズが $n$ 以下のどの入力 $I$ に対しても，アルゴリズム $A$ が高々 $g(n)$ 回のステップで停止することをいいます．どんなに意地悪な入力に対しても $g(n)$ 回で停止するといっているわけです．
逆にアルゴリズム$A$の時間計算量が $g(n)$ 以上であるとは，入力の列 $I_n$ が存在して，$|I_n|=n$ かつ $A$ で $I_n$ を処理すると停止するまでに $g(n)$ 以上のステップが必要である，ということです．両方が成り立つとき，単にアルゴリズム $A$ の時間計算量は $g(n)$ であるとかいいます．
空間計算量というのはアルゴリズムが停止するまでに使用する（または必要とする）メモリの容量のことです．
時間計算量は納期とか締め切りとかに直結するのでその大きさそのものに関心が持たれますが，空間計算量はコンピュータのメモリ容量以下でさえあれば問題ないので，その大きさそのものに関心が持たれることは少ないです．したがって空間計算量のことはあんまり考えないことも多いです．以降，この記事では計算量といったら時間計算量のことを指します．
ビッグオー記法
このように素朴に定義される計算量には，実のところ大きな問題があります．
まず，１つにはどれを基本ステップとみなすのか，あるいは実装するときにどういう言語を用いるかによって定数倍のブレが生じるという問題があります．できれば定数倍の差を気にしなくていいように定義したいのです．簡単な解決法は関数 $g$ の定数倍で割った同値類を考えることですが，それでもまだ解決できない問題があります．
2つめの問題とは次のようなものです．アルゴリズムの計算量が問題になるのは，入力のサイズ $n$ が十分大きいときだけです．$n$ が小さいときにはさっき無視した定数倍の違いが大きく効いてきますから，計算量を問うこと自体ナンセンスになってしまうのです．つまり，理論的に意味があるといえるのは「入力サイズ $n$ が大きくなっていくとき，アルゴリズムの計算時間の増加がどれくらいの速さであるか」ということだけなのです．
たとえば，計算時間が $n ^ 2$ に比例するというのと，$n(n-1)/2$ であるというのは同じだけの意味しかありません．これらを区別することに意味はないのです．
そこで，次のようにO記法というものを導入します．関数 $g$ に対して $O(g)$ というのは，ある関数の集合であって，定数倍の違いを除いて漸近的に $g$ よりも小さいものの集まりになっているようなものです．つまり，次の(1)(2)(3)は同値です．
(1) $f$ が $O(g)$ に属する
(2) ある定数 $N$ と $C$ が存在して，$n \geq N$ ならば $f(n) \leq C g(n)$ が成り立つ．
(3) $n \to \infty$ としたとき $f(n)/g(n)$ の上極限は有界．
ここで $O$ というのはオーダー(order)の頭文字です．
この記法により上記の問題はいちおうの解決をみます．
さらに，慣例的に $f \in O(g)$ というのを $f= O(g)$ と書くことを注意しておきましょう．$O(g) = f$ という書き方はしませんので，これは等号の両辺は交換可能であるべしというルールに反しているのですが，しかしこういう慣例なのです．
P
以上の準備のもとで，「本質的に効率的」という言葉の意味を定義していきましょう．
素朴な力任せ探索では，与えられた集合 $X$ に対して「 $X$ の部分集合の全体 $2 ^ X$ 」とか「 $X$ の要素の置換全体 $\mathrm{Aut} X$ 」とかいったものを何も考えずに虱潰しに探索していくということをやります．
これらの集合は，元の集合 $X$ に対してどのくらいのサイズになるかというと，具体的には $2 ^ X$ のサイズは $|X|=n$ とすると $2 ^ n$ ですし，$\mathrm{Aut} X$ のサイズは $n! := 1 \times 2 \times \cdots \times n$ です．知らない人向けに書いておきますが，$n!$ は階乗関数といいます．$n$ が十分大きいとき $2 ^ n \leq n! \leq 2 ^ {n \log_2 n}$ を満たしますので，指数関数 $2 ^ n$ より少し大きいという感じです．
したがって，素朴な力任せ探索を実行すると，入力のサイズ $n$ に対して指数関数的に大きな計算量が必要になりがちなのですが，指数関数は増加が急激であるため入力サイズ $n$ がちょっと大きくなっただけでもすぐ手に負えなくなってしまいがちです．これは組合わせ爆発と呼ばれている現象で，動画『フカシギの数え方』をご覧になった方ならご存じかと思います．
対して多項式関数はどんな指数関数よりも増加がゆっくりです．そこで「計算時間が多項式関数で抑えられる」アルゴリズムがあったら，それは全探索より本質的に速いと言ってよいのではないか？ということになります．
そこで，次のように定義します．判定問題 $Q$ は，あるアルゴリズム $A$ によって $O(n ^ c)$ ( $c$ は定数) 時間で解けるとき，多項式時間(polynomial time)で解けるといい，P に属する，といいます．そして，Pに属するということをもって，「効率的に解ける」ということであると宣言します．
実際には，最悪の場合に指数時間かかるからといって平均的に遅いとは限りませんし，指数時間であっても底が小さければ，小さなサイズの $n$ については問題なく解けたりしますし，そもそも多項式時間であっても指数が大きいとどうにもならなかったりするのですが，あまり細かいことを気にしてはいけません．実用の場面にも適用できる理論を構築するのは確かに大事ですが，実用的に重要だからといっていちいち気にしていては話がいたずらにごちゃごちゃするばかりです．勇気をもって大胆に「理論上はそれでいいのだ」と思い込みましょう．
これで上記の疑問を次のように書き直すことができます．
NPとco-NP
「離散最適化において中心的な位置を占める問い」であると書いたこれですが．
まだ曖昧なところがありますね．「こうした離散的な問題」のところです．「こうした問題とは何か？」というツッコミが当然考えられます．理論を構築しようという立場からの言い方をすれば，「多項式時間アルゴリズムを設計できる見込みがある程度には簡単で，かつ興味深い問題の多くを含む程度には難しい，適切な複雑さのクラスは何か？」ということですね．
逆にどういう問題を考える対象から除外するべきなのかという切り口から考えていきましょう．
オンライン最適化問題
実用的に意思決定の場面で現れる離散的な問題を全部扱いたいと思うなら，次のような問題も扱うことになりますね．
この手の，問題の入力がいっぺんにはわかっておらず，順次与えられていく形式の問題をオンライン最適化問題といいます．離散最適化の中の一分野でありまして，産業的にも頻繁に現れる重要な問題なのですが……このブログでは扱わないことにします．
なぜかというと，やはり少し異質だからです．いままで私は「できるだけ高速に解きたいという動機がある」というお話をしてきましたが，オンライン最適化問題においてはこの動機の部分が異なります．そもそも「時間をかければ解ける」という前提がオンライン最適化では崩れておりまして，「情報の不足をどう補うか」という固有の問題意識があります．根本にある動機の部分がこれほど異なる分野を同時に扱うのは無理があるかと思いました．
組合わせゲーム的な問題
先ほど「時間さえかければ解ける」という前提が崩れていてはいけないと申しましたが，ではこの前提さえあればいいのでしょうか．たとえば次のような問題はどうでしょうか？
将棋のルールをご存じない方，あるいは非形式的なトークには我慢ならないという方は競争的施設配置問題とかに代えて考えてください．*5競争的施設配置問題というのは，
出力：２人のプレイヤーが順に点を選んで店を開いていく．点 $i \in V$ に店を開設すると利益 $b_i$ が手に入る．ただし隣接する２頂点に店を開設することはできないし，同じ点には一度しか店を開設できない．後手がどういう手を打ったとしても，先手は必ず利益を $B$ 以上にすることができるだろうか？
……というように定義される問題です．要するに運要素のない有限の盤面で行われるある程度複雑な２人ゲームで「ある限られた手数の中でどちらかが必勝であるか？」を答える問題を考えてください．
この問題はゲーム木を書いてすべての場合をしらみつぶしに調べれば答えがわかりますので，確かに力任せ探索が可能な程度には易しい問題です．しかしこの問題は頂点被覆問題などとは少し違っていて，一般にはより難しい問題です．*6
何が違うのかというと，結論を納得してもらうのに必要な労力です．たとえば頂点被覆問題であれば，「サイズが $k$ 以下の頂点被覆が存在するか？」という問いの答えがYESであれば，実際にその頂点被覆を見せれば少しの計算で納得してもらえます．答えがNOだったときに納得してもらうにはすべての部分集合を目の前で試すような面倒な方法しかないかもしれないですけど，YESなら短い言葉で示せます．*7
しかし詰将棋のようなゲーム的な問題の場合はそうではなさそうです．答えがYESであり，先手が必ず勝てるときでも，場合分けをしてすべてのケースをつぶしていかなければ納得してもらえそうにありませんし，答えがNOの場合でも同じです．証明された事実ではありませんが，一般的に競争的施設配置問題をはじめとしたこの手の問題に対しては，答えを納得してもらう短い（つまり長さが多項式で抑えられるような）証拠を示すことはできないだろうと言われています．
こういう，答えがYESでもNOでも納得してもらう短い方法がない（あるいは，なさそうな）問題は，やはり考察対象から除外することにします．なぜなら，難しさが違い過ぎて，「多項式時間で解けるか？」という問いを立てるのがもはや不適切となり，「多項式領域で解けるか？」という問いに変えないといけなくなったりするからです．「効率的なアルゴリズム」の定義が通用しないのは困ります．*8
NPの定義
さて，以上の準備のもとでNPとco-NPというクラスを定めましょう．
NPとは，答えがYESとなるようなインスタンスに対して，多項式時間で検証できるような証拠が存在する判定問題のクラスのことです．co-NPはその補問題であり，答えがNOとなるようなインスタンスに対して，多項式時間で検証できるような証拠が存在する判定問題のクラスのことです．当たり前ですが解くことが効率的にできるなら解を検証するのも効率的にできるに決まっていますので，P $\subseteq$ NP かつ P $\subseteq$ co-NP が成り立ちます．
身近なイメージとしては，ナンバーロックを思い浮かべていただければ良いかと思います．0から9までの数を $n$ 桁選んで，正しい順列を見つければカチッと開くような錠前を考えてみてください．こういう鍵は解の候補が $10^n$ 個あるので，しらみつぶしに解を探すと鍵の長さ $n$ に対して指数関数的に長い時間がかかってしまいますが，しかし正しい解が本当に正しいことを確認するのはすぐにできますね．むしろすぐにできなければ困ります．
余談ですが NP $\cap$ co-NP というクラスにも意味があって，文献などによく登場します．これはYESインスタンスであってもNOインスタンスであっても短い証拠が存在して検証ができるという判定問題のクラスで，P 問題の次くらいに大人しくて与しやすい問題というイメージです．実際，NP $\cap$ co-NP に属する問題は良い特徴づけを持つと言います．ある問題が P なのか NP 完全なのか分からなくて途方に暮れているとき，良い特徴づけを持つことが示せるとだいぶ P 寄りに気持ちが傾くものです．
おっと，油断してたらだいぶ話が長くなってきましたね．まとめましょう．
大事なことは「答えの検証が効率的にできる」というクラスの難しさはちょうどよい塩梅である，ということです．効率的に解くという目標が多少の現実味を帯びる程度には簡単で，かつ興味深い問題の多くを含む程度には難しいクラスなのです．これは我々の目的にぴったりなので，最初に私がでっちあげた「中心的な問い」は次のように解像度を上げた形で書き直すことができます．
ここで終わっても良いのですが，さらに一工夫しておきましょう．NP問題という概念は判定問題に対して定義しましたので，このままですと探索問題や最適化問題の話をしづらくなります．そこで「判定問題ver. を考えたときにそれがNPに属するような探索問題や最適化問題」をひっくるめた概念であるNP型問題というのを定義しておきます．
NP型問題という呼称は一般的なものではありませんが，私のオリジナルでもないことに注意してください．*9
そうしておいて，先述の疑問も次のように書き直しておくことにします．
これでモチベーションがはっきりしました．
効率的に解ける問題
さて，今度はいま説明したこの分野の中心的モチベーションを敷衍して何が得られたか（得られなかったか）という話をします．
世の中解ける問題もあれば解けない問題もあるわけですが，離散最適化（組合わせ最適化）*10では実用上重要な問題の多くが「解けそうにないほど難しい」と言われています．しかし解けそうにないからといって諦めるわけにはいきません．そこで計算困難問題に対しては新しい設計思想が提案されてきました．これ以降，その一部を紹介していきます．
さきほど離散最適化という分野の中心的な問いは次のようなものだと書きました．
その後どうなったでしょうか．人類は快進撃を続け，次から次へと難問を組み伏せつつあるのでしょうか．それとも計算困難な問題を前にして己の無力さを嘆くばかりなのでしょうか．気になりますね．良いニュースと悪いニュースがありますけど，まず良いニュースから紹介します．いいニュースその１は，効率的に解ける問題のお話です．
他の分野での応用の話がでてきますが，これはもちろん意図的なものです．離散最適化という分野は，離散的な数理モデルから生じた他分野の問題を一手に請け負う，何でも屋のような分野です．したがって離散最適化における良いニュースは，どこかほかの分野の良いニュースに直結していますから，応用を書いた方が良いと思ったのです．
安定結婚問題
次のような問題を考えてみてください．
これだけだと「ずいぶんと世話好きなひともあったもんだなぁ」という印象を持たれるかもしれませんが，実はこれは2012年のノーベル経済学賞を受賞した研究が取り組んでいた問題そのものです．すごく産業的に重要な問題なのです．今回は状況がわかりやすいように男女の結婚を例にとって説明していますが，この種の問題はたとえば研修医の病院への配属を決めるときや，あるいは学生の研究室への配属を決めるとき，そして企業と応募者間の配属を決めるときなどに現れます．社会の仕組みやルールをどう作ればいいかを考えるときに離散最適化の考え方が有用であることを示す顕著な例と言えるでしょう．このように，異なる目的・好みを持つ複数のプレイヤーがいる状況で，アルゴリズムの設計・解析を行う分野のことを，アルゴリズム的ゲーム理論といいます．
この記事では詳細は省略しますが，この安定結婚問題に対する答えはYES（つねに駆け落ちを起こさせない結婚のさせ方，つまり安定マッチングが存在する）であることが知られており，しかもそれは入力の多項式時間で計算することができます．そのアルゴリズムはGale-Shapleyのアルゴリズムと呼ばれています．
Gale-Shapleyのアルゴリズムというのは実にシンプルなもので，以下の簡単な手続きからなります．
フリーな男性は好みの女性に順にプロポーズをしていき，
プロポーズされた女性が独身ならプロポーズを受け入れ，
プロポーズされた女性がすでに婚約していれば，より好きな方に乗り換える．残された男性はフリーになる．
おもしろいことに，この手続きで得られる結婚の割当は常に「男性にとっては可能な安定マッチングの中で最善」かつ，「女性にとっては可能な安定マッチングの中で最悪」になることが証明できます．*11私たちはいつも「プロポーズを受ける側，つまり選ばれる側の方が立場が強い」と思っていますが，構造上優遇されるのはつねに選ぶ方だというのは示唆的であり，ちょっと皮肉な感じもしますね．
線形計画問題
線形不等式によって表現される制約のもとで，線形な目的関数を最大化あるいは最小化する問題のことを，線形計画問題（Linear Programming）といいます．つまり，次のような問題のことです．
要求：ベクトル $x \in \Q_{\geq 0}^m$ であって，線形不等式 $Ax \leq b$ を満たす $x$ は存在するか．存在するなら，内積 $c \cdot x := \sum_{i=1}^m c_i x_i$ を最大化（または最小化）するものを求めなさい．
あからさまに応用がありそうな問題設定ですが，事実オペレーションズリサーチに応用があります．資源の制約のなかで，なにをどれだけ生産すれば利益を最大化できるかという，よく現れる問題に対する数理モデルとして有用です．また，より自明でない応用として，鋳型により製品を鋳造したいという状況で，「完成品をうまく取り外すことのできるような鋳型を設計できるか？」という問題の数理モデルになることが挙げられます．
解法
そしてこれが肝心なことなのですが，線形計画問題は多項式時間で解くことができます．主要なものだけ挙げると，楕円体法と内点法という二つの多項式時間アルゴリズムがあります．これは理論的にとても重要なことです．
なぜ「理論的に」とわざわざ断ったかというと，実用的には単体法というわりに高速な方法があって，それで困らないからです．むしろ多項式時間アルゴリズムの方が遅いこともあります．とくに楕円体法は遅く，実用上は使い物にならないとされています．*12
「なんだよそれ！理論間違ってるじゃん」と思われたかもしれませんが，理論は間違っていません．この見かけ上の矛盾の原因は，理論的な計算時間の解析が「最悪の場合にどれくらい悪くなるか」に依存していることあります．単体法は確かに「実用上遭遇するようなインスタンス」に対しては速いのですが，指数関数的に多くの反復を必要とするような病的な例を作ることができて，したがって多項式時間アルゴリズム（つまり理論的に速いアルゴリズム）ではないのです．
また，いくら「多項式時間」と言ってもその多項式の次数が大きければ実用的には指数時間アルゴリズムと同じく使い物にならない……ということも注意が必要なところです．楕円体法はどんなに意地悪な例に対しても多項式時間で走る代わりに，多項式の次数が高くて遅いというわけです．
ところで内点法は実用的にもなかなかに高速でかつ多項式時間なのですが，論文で見かけるのは楕円体法が圧倒的に多い気がしています．*13 なぜかはわかりませんが，おそらく楕円体法が「制約式が指数関数的にたくさんあっても，分離オラクルさえ解けるなら多項式時間で走る」というとても良い性質を持っているからでしょう．楕円体法は理論的にはすごく良い子なんです．
「理論的に速いアルゴリズム」が「実用上速いアルゴリズム」と一致しないのはきもちわるいので，個人的には単体法が高速で走るための条件がもっと詳しくわかるといいなあと思います．
LP緩和
話は変わりますが，見てわかる通り，線形計画問題の設定はちっとも離散的ではありません．従って素朴に考えると離散最適化とは関係がなさそうなのですが，実際にはとても重要な問題です．その理由のひとつは，この線形計画問題において変数 $x$ に「各成分は整数でなければならない」という制約を付け加えた整数計画問題(Integer Programming)を考えると，これが多くの離散最適化問題を含む一般的な問題になるという点にあります．
たとえば頂点被覆問題
要求：$G$ の頂点被覆 $S \subseteq V$ の中でサイズが最小のものを求めよ．
を例として整数計画問題としての定式化を行ってみましょう．各頂点 $v \in V$ ごとにこれを頂点被覆として選ぶかどうかの選択を行うわけなので，各頂点 $v$ ごとに $0$ か $1$ の値しかとらない変数 $x_v$ を用意します．そうすると $v$ が頂点被覆に選ばれることを $x_v = 1$ で表現することができます．
制約は，各辺 $e \in E$ がカバーされることです．つまり各辺 $e = (v, w)$ ごとに $x_v + x_w \geq 1$ という制約を設ければよいです．目的関数は頂点被覆のサイズですが，これはそのまま $\sum_{i \in V} x_v$ に一致します．
以上をまとめますと，頂点被覆問題は次のように整数計画問題で表現されます．（もちろん一通りではありませんが）
subject to :
各辺 $e = (v,w ) \in E$ ごとに $x_v + x_w \geq 1$
任意の $v \in V$ について $x_v \in \{ 0,1\}$
同様の定式化がほかの多くの離散的な問題でも行えます．
ここで変数の整数制約を緩和して，この場合ならたとえば $0 \leq x_v \leq 1$ としたものを，その整数計画問題のLP緩和といいます．ただしLPというのは線形計画問題(Linear Programming)の略です．LP緩和はLPなので多項式時間で解くことができて，元の問題に取り組むときの足掛かりにすることができます．
線形計画問題は便利だということがなんとなく伝わったでしょうか．
NP困難，NP完全
なるほど効率的に解ける問題については大いに進捗があったことがわかりました．では，解けない問題についてはどうなのでしょうか．
ある問題が「解けそうにない難しい問題だ」と結論付けるのは難しそうに思えますよね？「解ける問題だ」と示すのは実際に解いて見せれば済むことですが，試してみて解けなかったからと云って，「これは難しい問題なんだ」と言うわけにはいきません．自分よりずっと頭の良いひとの手にかかれば，あっさり解けてしまうかもしれませんからね！アルゴリズム設計者は，問題が解けないことを上司に言い訳するのに苦心し続ける運命にあるのでしょうか．
でも安心してください．それについても良いニュースがあります．良いニュースその２です．
というのもNP困難問題という概念がありまして．雑に説明すると「クラスNPのどの問題よりも難しい問題」という意味です．「より難しい」とはどういうことかというと，あるNP困難問題 $A$ が効率的に解けるなら，すべてのNP問題が効率的に解ける……ということです．さらに判定問題 $A$ がNPでありかつNP困難でもあるときは，NP完全であるといいます．
NP完全問題に対しては，大昔から恐ろしく頭の良いひとたちが効率的なアルゴリズムを設計する努力を続けていますが，いまだに誰ひとりとして成功していません．つまり，取り組んでいる問題がNP完全であることさえ示せれば，それだけでその問題が「難しくて解けそうにない」ことを示したことになります．
これでうるさい上司にも，あなたの能力不足のせいではないことが納得してもらえます．それは誰もが認める難しい問題なのです．
ついでながら，あるNP問題 $A$ がNP完全問題であることを証明する方法を補足しておきます．定義から直接示すのであれば，$A$ を解いてくれる素敵なマシン $M$ がもし存在すれば，任意のNP問題 $P$ が $M$ を使って解けることを示すことになりますが，それは大変な作業です．その代わりに，既にNP完全であることが判っている問題を利用します．
偉大な先人たちによって, 既に充足可能性問題(Satisfiability Problem, SAT)を筆頭にしたNP完全問題の長大なリストが作られています．その中から適当に都合の良い問題 $P$ を選んできて，$A$ が効率的に解けるなら $P$ も解けると言えばそれでOKです．
まったく先人の業績というのは素晴らしいものですね．
P≠NP問題
ここまで良いニュースを紹介してきましたが，そろそろ悪いニュースを紹介しなくてはならないでしょう．
さきほど，NP完全であることが判れば「誰もが認める難しい問題」だということが保証されるので効率的に解けなくても仕方ないと書きましたが，実は「NP完全なら効率的には解けない」ということはまだ証明されていません．経験的に難しいことが保証されるだけです．
「NP問題のうち，どれかひとつでも多項式時間では解けないことが証明できるか？」というのは，要するに「P≠NPが証明できるだろうか？」というのと同じことなので，これをP≠NP問題といいます．なお≠は「ノットイコール」と読みます．
これがわからないことには話が進まないほど，この分野では基本的で重要な問題なのですが，なにぶん数多の数学者の挑戦を悉く撥ね退け続けている難問でありまして……．多額の懸賞金もかかっているのですが，長いこと未解決問題であり続けています．
自慢できることではないですが，P≠NP問題に真正面から取り組まず，「もしもP≠NPならば」という但し書きを定理のステートメントに書き加えることでこの難問を棚上げにするのが業界の慣習になっています．*14
もしも万が一にでもP＝NPだったら，そういった定理すべてが水泡に帰すわけで，その可能性を考えると背筋が凍りますね．数学界隈でひそかにささやかれている怪談「有限非可換斜体論」を思い出します．かつては有限で非可換な斜体を研究する分野があったのだけど，「すべての有限な斜体は可換である」というWedderburnの定理が登場したために分野ごと葬り去られたという話です．あくまで怪談であってことの真偽は不明ですが……今のところ計算困難性の理論が同じ運命を辿らないとは誰も断言できません．
我々は実に危ない橋を渡っています．くわばらくわばら．
計算困難問題へのアプローチ
もしもP=NPだったら
P≠NP問題が解決しないことには我々は理論的な確信を得ることはできないと書きましたが，それではこの問題の解決まで我々はただ実存的不安に怯えるしかないのかというと，そんなことはありません．他にできることはあります．それどころか，P≠NP問題は視点によってはそう致命的でもないと思えるのです．
どういうことか説明しましょう．仮にP≠NP問題が解決したとします．大方の予想通りP≠NPだったなら，予想通りなんだから何の問題もありません．むしろ万々歳です．お赤飯です．そこでP=NPだったとしましょう．この場合は業界に激震が走ることでしょうが，実用的にはただちに何か大きな変化が起こるということはない気がします．
というのも，NP完全問題に対して多項式時間のアルゴリズムが存在することが仮に言えたとしても，それが構成的な証明とは限りませんし，仮に構成的だったとしても計算時間の多項式の次数 $d$ がモンスター群*15の位数のような，なまら大きい数である可能性が十分あるように思われるからです．そんなアルゴリズムは実用的にはとても効率的とは言えませんし，少なくとも当面は理論上の重要性しか持たない存在になりそうです．
実際，「NP完全なのかPなのか判っていなかった問題がPであることが判明したけれど，実用的にはそれほど反響がなかった例」というのはあるものです．たとえば素数判定問題がそうでした．NPかつco-NPであることは以前から知られていて，Pであるかどうかが未解決でした．多項式時間アルゴリズムが開発されてPであることが証明された*16ときにはかなり話題になったそうですが，多項式の次数が高いので実用的には以前から知られている方法の方が速く，その影響力は理論的な範囲にとどまりました．
また，線形計画問題（の判定問題版）もPであることが判明する前はNPかつco-NPであることしか分かっておらず，解くときは単体法で解かれていました．この単体法は前述の通り最悪の場合には指数時間かかるのですが，実用的にはそれなりに高速で走ることが知られています．やがて楕円体法が開発されてPであることが証明されたのですが，楕円体法は実用的には遅いですので，この成果による実用上の恩恵はほぼなかったのではないかと思われます．理論的には重大な業績なのですが．
要するに，P≠NP問題がどのように解決されようと，離散最適化界隈の現状が劇的に変わることはないだろうということです．相変わらずかつてのNP完全問題はPより実用上難しい問題であり続けるでしょうし，それまで数学者たちが積み重ねてきたものが一気に無用になるということもなかろうと思います．前節ではちょっと脅かしましたけど，結局はそういうことです．
新たな設計思想
実用的にはP≠NP問題よりもっと気を配るべきところがあります．それは，普通はNP困難だからといっておとなしく諦めるわけにはいかない……という点です．実用上重要な多くの問題がNP困難であるとなればなおさらです．悪あがきと言われようと邪道と言われようと，とにもかくにも解いて解を出力したいですよね．
そこでNP困難性をなんとか「くぐり抜ける」方法を考えたくなります．NP困難問題であることによる障害は次のように，複合的なものです．
ですから，どれか一つの条件を諦めれば解ける可能性はありますし実際解けることがあります．条件ごとに見ていきましょう．*17
最適解を返すことを諦める：これが近似アルゴリズムと呼ばれる分野の基本的な発想です．最適解に拘らず，最適解に近いことが保証された解で手を打とうじゃないかというアイデアです．
多項式時間で解くことを諦める：計算時間を多項式時間までは下げられないなら指数時間で妥協することにして，せめてその底を改善しようというアイデアです．これは指数時間アルゴリズムと呼ばれる分野に繋がっていきます．$2$ の $n$ 乗じゃなくて $1.4$ の $n$ 乗にできると嬉しいとか，そういうことを考えるわけです．
最悪の入力に対しての保証を諦める：悪い入力と良い入力は入力サイズこそ同じですが，「素性のよさパラメータ」みたいなものが違うと思って，それを計算時間の解析に含めてしまうというアイデアです．パラメータ化計算(Parameterized Computation)と呼ばれる分野に繋がっていきます．なおこの分野における目標は，計算時間の素性の良さパラメータに対する依存度を下げることで，うまく行った場合は固定パラメータ容易(Fixed Parameter Tractable)であるといったりします．
このように，いまの数学ではNP完全問題のことは基本的なこともまだ理解できていないと言っても，万策尽きたわけでは全くなく，まだまだ悪あがき…もとい工夫の余地はあり，活発に研究が行われているのです．
設計思想の紹介
前節でさらっと紹介した設計思想にはそれぞれおもしろいところがありますので，もう少し詳しく説明します．
近似アルゴリズムとは
ある最適化問題に対して，返す解が常に最適解にある程度近いことが証明されている多項式時間アルゴリズムのことを近似アルゴリズムといいます．
「証明されている」というところが結構重要で，証明がない場合はヒューリスティクスといいます．ヒューリスティクスと近似アルゴリズムの違いは実は不確定であり，今までヒューリスティクスだと思われていたものが新たな解析手法の出現により近似アルゴリズムと認められることがあります．
「最適解にある程度近い」かどうかはどうやって測るのかというと，最適解との値の比や差の絶対値をみて測るのが一般的です．アルゴリズムの返す値を $A$, 最適解の値を $OPT$ とすると，$OPT / A$ とか $|OPT - A|$ の最悪の場合の大きさを見積もるわけです．アルゴリズムの返す解と，最適解との離れ具合の見積もり値は，比の場合は近似比と呼ばれ，差の絶対値の場合は絶対誤差などと呼ばれます．*18欲を言えば絶対誤差が定数のアルゴリズムが設計できればいちばん嬉しいのですけど，実際には理論上不可能であることが多いです．絶対誤差が定数の近似アルゴリズムは，古典的なごく少数の問題でしか知られていません．したがって，近似比を抑えるアプローチの方がずっと一般的です．
近似アルゴリズムという分野の理論的な目標は雑に分けると次の２つです．
NP困難な問題に対して，多項式時間という制約の中でできるだけ近似精度の高いアルゴリズムを設計したい，
そしてこれ以上良くは近似できないという近似閾値が正確にどこにあるのかを知りたい．
この「多項式時間」という計算時間は以前の記事で「効率的で，実用的にも許容できる」と書きましたが，実際のところ近似アルゴリズムに関してはそうでないことも多いです．この分野では，シンプルさや計算時間を代償にして近似保証を精緻化していくことが広く行われているものですから，多項式は多項式でも係数や次数が大きすぎて実用的ではないことがままあるのです．理論的にはそれで全然構わないのですけど，この記事では近似アルゴリズムを「NP困難問題をとにもかくにも解くための設計思想」として導入したので，この記事の趣旨的には大いにまずいということになります．
では近似アルゴリズムの理論は役に立たないのかというとそんなことはありません．近似アルゴリズムを設計するための理論は往々にして解析のためにも役立つものです．ヒューリスティクスを解析して近似保証を行うことで，単なるカンや慣習のようなものに理論的基盤を与えることができます．
厳密アルゴリズムとは
近似解ではなく厳密解を求めるアルゴリズムのことを厳密アルゴリズムと呼ぶことがあります．目的が似ている分，手法もだいぶ似通ってきますが，大きく分けて３つの異なるアプローチがあるように思います．
パラメータ付き前処理
前処理とは，入力のインスタンスに対して多項式時間アルゴリズムで処理を行い，より小さな同値なインスタンスに還元することを指します．kernelizationと呼ぶのが普通ですが，どう翻訳したものかわからなかったのでここでは単に「前処理」または「パラメータ付き前処理」と呼ぶことにします．
前処理アルゴリズムでは，適当なパラメータ $k$ によって出力のサイズが抑えられることが必要です．なぜわざわざ新しいパラメータを考える必要があるかというと，扱う対象がNP困難問題ですので「すべての入力に対して一様に」サイズを小さくすることができそうにないからです．適当なパラメータを用いれば出力サイズを評価することが往々にして可能であるという発見は，発見当時は大きな衝撃だったみたいですね．*19
具体例をお見せしないと説明しにくいので，いつものように頂点被覆問題を例にして説明しましょう．頂点被覆問題は自然な形では最適化問題ですが，解のサイズをパラメータにすることで，次のように判定問題に加工しておきます．*20
パラメータ：解のサイズ $k$
要求：サイズが高々 $k$ であるような頂点被覆 $S \subseteq V$ は存在するか？
前処理というのは，こういった問題に対して「常に解が含むような頂点」や「絶対に解には含まれない頂点」，「それを含む解が必ずあるような頂点」がないかということを考え，それらを除外してしまう一連の還元プロセスからなります．
この問題の場合，たとえば次数が $k$ より大きい頂点は除外することができます．
なぜかというと，次数が $k$ より大きい頂点をもし含めなかったとしますと，その点に隣接している頂点すべてを頂点被覆に含める必要がありますが，しかし，それだけで「高々 $k$ 個まで」という制約を破ってしまうからです．したがってそういう頂点は被覆に必ず含める必要があり，考える対象から外してよいわけです．
この還元ルールにより，入力グラフの各点の次数が $k$ 以下になるようにできます．このときもし望みの頂点被覆 $S$ が存在するならば
ですから，入力グラフの辺のサイズは $k^ 2$ 以下であることがわかります．ただし $d(v)$ というのは点 $v$ の次数のことです．この出力のサイズの評価 $|E| \leq k^ 2$ の右辺が入力サイズには依存せず，パラメータ $k$ にしか依存しないという点が重要なところです．
一般に，アルゴリズム $A$ がパラメータ付き判定問題 $P$ に対する前処理アルゴリズムであるとは，*21
$A$ は $P$ の入力 $(I, k)$ に対して同値な別の入力 $(I', k')$ を返すアルゴリズムであって，
$A$ は $|I| + k$ に関する多項式時間で走り，
かつ出力のサイズ $|I'|$ と出力のパラメータ $k'$ がともに $k$ だけの関数 $g(k)$ で抑えられる
ということであると定義されます．そして出力サイズの上界を定める関数 $g$ が小さい（つまりゆっくりと増加する）ほど，その前処理アルゴリズムは優れているとされます．*22
指数時間アルゴリズム
さて前処理によって「より小さなインスタンスに帰着できる」という話をしましたが，帰着してその後どうするのでしょうか．今度こそ腕力でごりごり解くしかありませんね？そのための手法がまさに指数時間アルゴリズムです．
一般的には別に前処理と対をなすアプローチとみなされているわけではありませんが，指数時間アルゴリズムと対にして紹介しておかないと「前処理はただ還元しただけで終わり！という中途半端なアルゴリズム」という印象を持たれてしまいそうだったので，このブログでは指数時間アルゴリズムは前処理と関連付けて紹介することにしました．
さて指数時間アルゴリズムですが，これは名前の通り指数時間を許してできるだけ（漸近的に）高速なアルゴリズムを設計することを目指す分野です．思えば $2 ^n$ の計算時間が $1.4143 ^n$ に改善されれば，指数関数的に大きく改善されていることになりますし，実用的に解ける入力のサイズはほぼ２倍になるわけです．指数関数の底を改善するというのは，単なる悪あがきではなく十分に有用で実りのあるアプローチであると思われます．
本質的に近似が難しいといわれる問題でも，自明な全探索より高速なアルゴリズムを開発できることはあります．たとえば独立集合問題は一般の場合は自明な近似しかできない*23のですが，指数時間になることを許せば全探索より高速なアルゴリズムが作れます．この分野の嬉しいところのひとつはそういう点です．
計算容易性の拡大
今までNP困難な問題は多項式時間では解けそうにないという話をしてきましたが，問題の入力がある種の良い性質を持つような状況に限定すれば解けることもあります．たとえばいつも例に挙げている頂点被覆問題ですが，これは入力グラフが森（閉路のないグラフのこと．連結な森のことを木といいます）であるときには多項式時間で解けます．つまりこの問題の難しさは，グラフが一般には森ではないことに由来する成分があるわけですね．
ここで次の疑問がわいてきます．「グラフが森っぽい構造を持つときには，そうでないときより高速で解けてもいいのではないか？」つまり，グラフに対してそのグラフの「森っぽさ」をパラメータ $k$ として定量化することができれば，$k$ が小さいときには多項式時間で解けるのではないか？ということです．詳細は省略しますが，結論から言うとこれは可能です．
木幅と木分解という概念がありまして，先ほどから述べている「グラフの森っぽさ」という雑な概念をきちんと定式化することができます．そして入力グラフの木幅 $k$ と木分解 $(T, \{ V_t \})$ が入力として与えられていれば，頂点被覆問題は $O(4^{k+1} k n)$ くらいの時間で解くことができることが知られています．*24 これはつまり，$k = O(\log n)$ のときには全体が多項式時間で解けることを意味します．
このように，問題に付随するパラメータ $k$ が小さい定数であれば多項式時間で解けるというのみならず，多項式時間で解くことを可能にするために必要な $k$ の上界が定数より真に大きい関数にまで拡大できるとき，その問題はパラメータ $k$ について固定パラメータ容易であるといいます．
以上の説明は直観的なものであって，正式には「 計算時間がある計算可能な関数 $f$ により $f(k) n^{O(1)}$ と書けるアルゴリズムがあるとき」に固定パラメータ容易であるといいます．英語ではFixed Parameter Tractableと言いまして，頭文字をとってFPTと言ったりもします．FPTアルゴリズムを設計する際の目標は，できるだけ大きな $k$ について多項式時間で走るようにすることに設定するのが一般的です．ちなみに，パラメータ $k$ が定数なら多項式時間で解ける，というだけならXPであるといいます．XPとFPTの違いは，境界線が定数関数かそうでないかというところですね．
ここまで意図的に伏せていましたが，実は前処理アルゴリズムが存在することと，その問題がFPTであることは同値です．にもかかわらずここではあえて全く違うものとして紹介してみたわけですが．なぜかというと，前処理アルゴリズムは「できるだけ小さいインスタンスに還元する」という独自の目標・価値観を持っているので，目的を重視して分類するこのブログの方針から言って分けた方が好ましいと思ったからです．
まとめと振り返り
お疲れ様でした．ここまで長文に付き合っていただきありがとうございます．
まとめると，この記事では離散最適化という分野が「どういう問題を解こうとしているのか」という話をしてきました．
離散的な問題をなるべく高速に解きたい．解けない問題があれば「高速には解けない」ことを証明したい．現状では「高速には解けない」ことの証明はできていないけれども，「高速には解けそうにないほど難しい」くらいなら定義・証明できるようになってきた．そして「高速には解けそうにない」問題に対しても，なんとか解を得るためにさまざまな設計思想のもとアルゴリズムが開発されてきている．……そんな話をここまでしてきました．
設計思想の話にかまけて計算論的ゲーム理論とか計算幾何学の話があまりできなかったのは残念でした．また機会があればそちらについても書きたいです．
Appendix 補足
二分探索の疑似コード
アルゴリズムの説明をするとき適当なプログラミング言語（たとえばCとかPythonとかJuliaとか）で説明すれば紛れがなくてよかったかもしれませんが，このブログでは実装についての議論はあまりしませんので，なるべく自然言語に近く読みやすい形式で書きたいと思います．
そこでここでは，アルゴリズムを自然言語でわかりやすく記述するためのフレームワークである，疑似コードについて説明します．
疑似コードがなんであるかということは，言葉で説明するより実例を見せた方がわかりやすいと思いますので，まず卵の問題に対する二分探索アルゴリズムを疑似コードで書いたものをお見せします．こんな感じです．
この疑似コードを例として，疑似コードの構成要素を説明していきましょう．
行番号とコメント
まず左に番号が振ってあるのがわかると思いますが，これは行番号と呼ばれるもので，実行順序を意味しています．行番号が若いものから順に，ひとつずつ実行されるということです．
途中で行頭に//と書かれた文が登場するのがわかると思いますが，これはコメントです．コメントは，アルゴリズムの実行内容とは関係がありません．コードをそのまま書いてしまうと読みづらいので，直観的にイメージしやすいように説明を加えるためのものです．普通コメントは行番号を跨がないように書くものですが，このコードでは見やすさを優先して独立行でコメントを書いています．
whileループ
途中でwhileと書いてあるのがわかると思います．これは「ある条件が満たされている限り，doからendwhileまでの指示を繰り返し実行し続ける」というものです．whileからdoまでに書いてあるのが繰り返し条件であり，doからendwhileまでに書いてある内容が繰り返される指示です．whileの中に恒等式を入れてしまうと無限ループになることに気を付けてください．
さらにwhileからendwhileまでの文章が，一段下がっていることに気づかれたでしょうか．これはインデントというもので，whileループにより繰り返すよう指示されている内容がどこからどこまでなのかを視覚的にわかりやすくするためのものです．疑似コードの書き方の流派によっては，インデントだけでwhileの範囲がわかるからといってendwhileを省略することもあります．
if文
if文は，条件分岐を表現するためのものです．ifからthenまでに書かれているのが条件文で，条件文が真であるときはthen以降のインデントされた内容を実行するよう指示しています．else以下は，条件文が偽のときに実行する内容であると指示しています．
elseを使わない場合もあります．このときは，条件文が偽のときにはif文がスルーされるだけになります．
複数の条件文による分岐を表現したいときにはelseifを使用します．elseif 以下の条件文２は最初の条件文１が偽であったときに真偽の判定がなされ，真であったときにはelseif以下の指示が実行されます．
elseifは複数使うこともできます．その場合もやはり上記と同様に分岐が行われます．
if文についてもやはりインデントは必要で，インデントがあれば適用範囲はわかるからといってendifを省略することがあります．
変数
最初に「初期化」されている $l$ と $u$ という記号がありますが，これは変数というものです．数学で変数というと関数の引数を受けとるものとか，未知数を仮に置いたものとかいうイメージがありますが，疑似コードにおける変数は「値を格納しておく箱」という感じです．アルゴリズムの実行中に値が代入されて変わっていくのが普通で，後で使う情報をしまっておくところという意味合いもあります．初期化というのは，変数を新しく用意したときに最初に値を入れておくことです．
疑似コードでは変数の型を宣言する必要はありませんが，ある集合 $X$ の部分集合を格納する変数なのか，それとも整数を格納する変数なのかといったことはアルゴリズムの実行中に変えないように気をつけてください．
変数の値が等しいかどうか比較するときにプログラミング言語によっては==という記号を使いますが，このブログでは通常の等号=を使用します．その代わりに変数に値を代入するときには $\leftarrow$ という記号を使います．たとえば $x$ に３を代入するのであれば，$x \leftarrow 3$ と書くことにします．
Forループ
繰り返しを記述する疑似コードにはいろいろあるのですが，while以外で主要なもののひとつにForループがあります．Forループは，条件文でなにかの変数とその動く範囲を指定し，指定された範囲全てにわたって変数を走らせながら所定のコードを繰り返し実行するよう指示するものです．
for文についてもやはりインデントは必要で，インデントがあれば適用範囲はわかるからといってendforを省略することがあります．
returnとbreak
さきほど挙げた二分探索アルゴリズムの最後にreturnという文があります．これはアルゴリズムを停止して，指定した変数の値や真理値を返すことを指示するものです．たとえ疑似コードがその後に続いていようと，returnが実行されたら強制的に終了になります．
たとえば以下のようなコードがあったとすると，条件文が真なら $x=3$ が返ってきます．$x$ に５を代入する操作がretunによる強制終了の後だからです．
逆に条件文が偽なら，if文はスルーされるので $x=5$ が返ってきます．
似たような挙動をするコマンドとしてbreakがあります．これは，forループやwhileループなどの繰り返し操作を途中で抜けるためのコマンドです．breakが実行されると，そのとき実行中だったwhile(for)ループのendwhile(endfor)にジャンプします．
自己リダクションの疑似コード
自然言語による解説では納得できなかったひとのために疑似コードを書いておきます．
*1:この卵の問題は有名なパズルで，様々な派生形が知られています．出典はわかりませんでした
*2:このセクションを書くにあたっては岡本吉央先生の2019年後期の授業『離散最適化基礎論 第 1回 アルゴリズム的問題解決と計算複雑性』のスライドを参考にしました
*3:この問題はParameterized Algorithmsからの引用です
*4:自己リダクション可能性についての 記述はVazirani「近似アルゴリズム」の付録を参考にしました
*5:競争的施設配置問題についての記述は，アルゴリズムデザインの第9章第5節あたりを参考にしました
*6:注意：組合わせゲームでも必勝法がわかっているものは存在します
*7:注意：頂点被覆問題の場合は，入力グラフが二部グラフである場合は多項式時間で解けることが知られていますので，一般のグラフの場合の話です
*8:注意：競争的施設配置問題は実際に多項式領域で解くことができますが，それほど自明ではありません
*9:私はこのセクションを書くにあたって，渡辺治さんの記事「NP型問題の近似解法の可能性について」を参考にしました．
*10:組み合わせ最適化とは書かないらしいです．慣用的に組合わせと表記します．
*11: アルゴリズムデザイン の第1章1節を参照のこと．あるいは安定マッチングの数理を参照のこと
*12: Korte Vygenの記述から．
*13:とくに近似アルゴリズム界隈ではそうだと思います．私の勝手なイメージなので間違っているかもしれませんが
*14:とくに近似不可能性の理論で顕著だと思います
*15:最も大きな散在型有限単純群のこと．その位数は 80恒河沙8017極4247載9451正2875澗8864溝5990穣4961𥝱7107亥5700京5754兆3680億0000万0000．数学的に深い意味のある最も大きな数字かもしれない．
*16:Agrawal, Manindra, Neeraj Kayal, and Nitin Saxena. "PRIMES is in P." Annals of mathematics (2004): 781-793.
*17:補足：乱択アルゴリズムが紹介されていないのは意図的なものです．乱択は，アルゴリズムの設計思想というよりは解法やヒューリスティクスの一種として紹介したいと思っているからです．異論は認めます
*18:絶対誤差という呼び方は Williamson Shmoys２章９節での記述に倣いました．しかし絶対誤差という用語が一般的なものかどうかは自信が持てないので，ここだけの用語だと思ってください．
*19:この記述はParameterized Algorithmsを参考にして書かれています
*20:選ぶパラメータは解のサイズである必要はありませんが，よく選ばれるのは解のサイズです．
*21:kernelizationに近似の概念を持ち込んだlossy kernelizationというものも定義されるのですが，この記事ではそこまでは扱いません．
*22:kernelizationとして線形時間で走るものしか認めない等のアプローチもありますが，この記事ではそこまで扱いません
*23:最大独立集合問題は，最大クリーク問題と等価です．最大クリーク問題の近似困難性については以下を参照のこと．Johan Håstad "Clique is hard to approximate within $n^{1−ε}$," Acta Mathematica, Acta Math. 182(1), 105-142, (1999)
*24:アルゴリズムデザインの第10章4節の内容から
