計算量に関して - <a href="http://itpro.nikkeibp.co.jp/article/COLUMN/20070618/275029/">矢沢久雄の情報工学“再”入門</a>を祝す

2007/07/01 改稿. NP問題の定義を追加.

家で勉強してた. 符号のリスト復号に詳しくなった.
矢沢久雄の情報工学“再”入門第1回アルゴリズムと計算量---「計算量理論」を理解し，アルゴリズムを評価するという記事を見て, 後半がダメダメなので突っ込み. なんかこういうツッコミしか日記にしないのはどうかと思うが, ブックマークもちらほらされているので誤解を広めないためにもツッコミを入れておく.

概要

前半のページ1とページ2は分かりやすく導入としては良い教材であると思う. *1
矢沢氏の文章ではNP問題およびNP完全問題の定義が曖昧である. 用語が不正確な為, 奇妙なことを書いている. (矢沢氏が定義を間違って覚えている可能性もある.)

引用

解けない「巡回セールスマン問題」

アルゴリズムとは問題を解く手順である。これを裏返すと，アルゴリズムの計算量は，問題の複雑性を示す尺度だとも言える。計算量理論では，計算量の大きさから問題の複雑さを分類したものを「計算量クラス」と呼ぶ。計算量クラスには，「クラスP」と「クラスNP」がある。
クラスP（Polynomial）は，決められた手順通りに処理を進めれば解ける問題の集合である。このクラスPに属する問題を「P問題」と呼ぶ。「配列の中から目的のデータを見つける」や「配列の要素の平均値を求める」といった問題は，クラスPに属するP問題だ。
これに対してクラスNP（Non-deterministic Polynomial）は，処理の手順に膨大な選択肢があり，その中から1つの手順を選んで，運が良ければ解けるというような問題の集合である。クラスNPに属する問題を「NP問題」と呼ぶ。
さらに，クラスNPに属する問題の中でも，特に複雑な（簡単には解けない）問題を「NP完全問題」と呼ぶ。NP完全問題として有名なものには，「巡回セールスマン問題」，「ナップザック問題」，「ハミルトン閉路問題」，「箱詰め問題」，「彩色数問題」，「論理式の充足可能性問題」などがある（個々の問題の詳細は，市販のアルゴリズム辞典などを参考にして欲しい）。
ここでは例として，「巡回セールスマン問題」を紹介しよう。巡回セールスマン問題とは，セールスマンが複数の訪問先を巡回する場合に，最短距離で巡回できる「順序」を導き出す問題である。
例えば10件の訪問先があった場合，1件目の訪問先に10通り，2件目の訪問先に9通り，3件目の訪問先に8通り……，9件目の訪問先に2通り，10件目の訪問先に1通りの選択肢がある。したがって，順路のパターンは10×9×8×……×2×1＝10!で，362万8800通りの選択肢となる（計算量はO(n!)だ）。
この選択肢の中から，1つだけを選ぶにはどうしたらよいか。362万8800通りの距離をすべて算出し，その中から最も短い選択肢を選べばよい。しかし，この計算には膨大な時間がかかる。またもし訪問先が100件だったら，スーパーコンピュータを使っても何万年も計算し続けることになる。つまり，この問題はNP問題（NP完全問題）として扱われる。
なお，P問題のように，決められた手順通りに処理を進めれば必ず解ける問題に対応するアルゴリズムを「決定性アルゴリズム」，NP問題を解くアルゴリズムを「意思決定アルゴリズム」と呼ぶ。前者は実際のプログラミングで使う馴染みのあるアルゴリズムだが，後者はプログラミングで使うことはまずない。
現在の情報工学では，与えられた問題がNP問題かどうかを証明できない。つまり，巡回セールスマン問題のようにNP問題だと言われているものであっても，本当は簡単なアルゴリズムで解けるP問題かもしれないのだ。それをNP問題だと思っているのは，単に“人間の頭が悪い”せいで問題を解くアルゴリズムが考え出されていないだけ，という議論がある。
言うまでもなくコンピュータは機械だ。しかし，その機械が解くのは実社会の人間的な問題であり，問題を解くアルゴリズムを考案するのも結局は人間である。コンピュータの世界に深入りすればするほど，コンピュータの人間臭さが見えてきて，ますますコンピュータに愛着を感じることだろう。

本体

NPの定義

アルゴリズムとは問題を解く手順である。これを裏返すと，アルゴリズムの計算量は，問題の複雑性を示す尺度だとも言える。計算量理論では，計算量の大きさから問題の複雑さを分類したものを「計算量クラス」と呼ぶ。計算量クラスには，「クラスP」と「クラスNP」がある。
クラスP（Polynomial）は，決められた手順通りに処理を進めれば解ける問題の集合である。このクラスPに属する問題を「P問題」と呼ぶ。「配列の中から目的のデータを見つける」や「配列の要素の平均値を求める」といった問題は，クラスPに属するP問題だ。
これに対してクラスNP（Non-deterministic Polynomial）は，処理の手順に膨大な選択肢があり，その中から1つの手順を選んで，運が良ければ解けるというような問題の集合である。クラスNPに属する問題を「NP問題」と呼ぶ。

初めに計算量クラスを整理する. 186::Diary - 2006/08/26 - 一般人無双R: PとかNPとかで悩んでますで使ったものを流用する. *2

問題には二種類ある. (近似問題とかプロミス付判定問題とかを考えるのは後にする).
言語をL, インスタンスをxとする.

判定問題: yes/noで答える問題. 具体的にはx∈Lかどうかを判定する.
探索問題: 何かを求める問題. 言語Lから作られた二項関係 $R_L$ について, $(x,w)\in R_L$ となるようなwを見つける問題. (例: 自然数が入ったリストを与えられたときに最大値を求める問題例: 自然数が与えられたときにその素因数のリストを求める問題.)

まず, PやNPは判定問題しか含まない. よって矢沢氏の表現は正確ではない. 「配列の中から目的のデータを見つける」という問題は探索問題である*3. 図では右側のFPに入る. (「配列の中に目的のデータが存在するか」という問題ならば判定問題である.)
判定問題のみを含むとしてもNP問題の定義が曖昧である. 処理の手順に膨大な選択肢があり，その中から1つの手順を選んで，運が良ければ解けるというような問題の集合であるという定義だと, 入力長をnとしたときに $2^{2^n}$ 時間掛っても良いことになる. このような問題はNPに含まれない可能性がある. 検証に掛かる時間か, 非決定性アルゴリズムを用いると多項式時間で解けるかの定義で良いのではなかろうか.

普通は以下のように定義する.
言語L∈NPの定義:

検証を用いた定義
- ある決定性多項式時間アルゴリズムMが存在し以下が成立する.
  - $x\in L$ ⇔ある証拠wが存在し, $|w|\in {\rm poly}(|x|)$ かつM(x,w)=yes
  - $x\not\in L$ ⇔任意の ${\rm poly}(|x|)$ ビットの文字列wについてM(x,w)=no
非決定性アルゴリズムを用いた定義
- ある非決定性多項式時間アルゴリズムMが存在し以下が成立する.
  - $x\in L$ ⇔少なくとも一つyesを返すパスが存在する.
  - $x\not\in L$ ⇔全てのパスでnoを返す

非決定性による分岐を木構造として考えるのでパスという言い方をする.
下の定義の場合, 木の深さは高々 ${\rm poly}(|x|)$ である. よって分岐の回数は高々 ${\rm poly}(|x|)$ となっている. なので高々 $2^{{\rm poly}(|x|)}$ 回の総当たりを行えば決定性アルゴリズムでシミュレート出来る. この場合 $2^{2^n}$ 時間掛かることは許されない.

NP完全の定義

さらに，クラスNPに属する問題の中でも，特に複雑な（簡単には解けない）問題を「NP完全問題」と呼ぶ。NP完全問題として有名なものには，「巡回セールスマン問題」，「ナップザック問題」，「ハミルトン閉路問題」，「箱詰め問題」，「彩色数問題」，「論理式の充足可能性問題」などがある（個々の問題の詳細は，市販のアルゴリズム辞典などを参考にして欲しい）。

まともな定義を書いておく. 問題がNP完全であるとは, NP問題でありかつ任意のNP問題がその問題に多項式時間で帰着出来ること. NP完全問題が多項式時間で解けると任意のNP問題が多項式時間で解ける. なので難しそうと思われている.

ここでは例として，「巡回セールスマン問題」を紹介しよう。巡回セールスマン問題とは，セールスマンが複数の訪問先を巡回する場合に，最短距離で巡回できる「順序」を導き出す問題である。
例えば10件の訪問先があった場合，1件目の訪問先に10通り，2件目の訪問先に9通り，3件目の訪問先に8通り……，9件目の訪問先に2通り，10件目の訪問先に1通りの選択肢がある。したがって，順路のパターンは10×9×8×……×2×1＝10!で，362万8800通りの選択肢となる（計算量はO(n!)だ）。
この選択肢の中から，1つだけを選ぶにはどうしたらよいか。362万8800通りの距離をすべて算出し，その中から最も短い選択肢を選べばよい。しかし，この計算には膨大な時間がかかる。またもし訪問先が100件だったら，スーパーコンピュータを使っても何万年も計算し続けることになる。つまり，この問題はNP問題（NP完全問題）として扱われる。

何がつまりなのか分からない. NP完全問題であることは自明ではない.

意思決定アルゴリズム

なお，P問題のように，決められた手順通りに処理を進めれば必ず解ける問題に対応するアルゴリズムを「決定性アルゴリズム」，NP問題を解くアルゴリズムを「意思決定アルゴリズム」と呼ぶ。前者は実際のプログラミングで使う馴染みのあるアルゴリズムだが，後者はプログラミングで使うことはまずない。

NP問題を解くアルゴリズムを「意思決定アルゴリズム」と呼ぶというのは変だろう. 普通に「非決定性アルゴリズムなら多項式時間で解ける」でいいんじゃないのか. 「意思決定アルゴリズム」って別の分野で意味付けされてる気がする.

L∈NPの証明とP!=NP予想の話

現在の情報工学では，与えられた問題がNP問題かどうかを証明できない。つまり，巡回セールスマン問題のようにNP問題だと言われているものであっても，本当は簡単なアルゴリズムで解けるP問題かもしれないのだ。それをNP問題だと思っているのは，単に“人間の頭が悪い”せいで問題を解くアルゴリズムが考え出されていないだけ，という議論がある。

巡回セールスマン問題 (判定版) がNP問題であることの証明

入力: 重み付グラフG=(V,E,c)と, 閾値k
出力: 全ての頂点を回る行程が存在する場合その中にコストがk以下のものがあるかかどうか
略証:
- 証拠判定器Mを以下のようにして作る.
  1. 証拠が行程で無い場合, noを出力. 行程のコストがk以下で無い場合, noを出力.
  2. 行程のコストがk以下の場合, yesを出力.
- 証拠判定器の計算時間は明らかに多項式時間.
- yesインスタンスについては, コストがk以下の行程を証拠とする.
- noインスタンスについては, コストがk以下の行程が存在しないので, 証拠判定器を騙すことはできない.