4部作その2。組み合わせ最適化第二版のp419~421の理解メモです。前回の決定問題の知識を前提に記事を書いています。
- 作者: B.コルテ,J.フィーゲン,浅野孝夫,浅野泰仁,小野孝男,平田富夫
- 出版社/メーカー: 丸善出版
- 発売日: 2012/02/29
- メディア: 単行本
- クリック: 5回
- この商品を含むブログ (1件) を見る
Nondeterministicについてちょっと小話
ちょっとわかりにくいのがNPですね。Not Pではありません。この話題に入る前にNondeterministic Turing Machineはドラえもんの秘密道具並みにヤバイ存在だということを頭に入れておくと、理解が深まります。NP問題を多項式時間で解くとされる「非決定性チューリング機械」は思考実験的アナロジーであり、任意のNP問題の非決定性アルゴリズムを多項式時間で解く計算機は実存していません。
またNondeterministicという単語が一般的なシステム用語と少しスコープが違う使われ方をしているように感じます。*1
- イメージとしてはこんな感じです。
- △常に同じ答えを出さない
- ⭕️常に最良の乱数を選ぶことができる
NPとP
クラスNPでは、多項式時間アルゴリズムは要求されず、任意のyes-インスタンスに対してのみ多項式時間で検証できる証明の存在だけが要求される。(p421)
証明検証アルゴリズムの箇所にも書いたが、Pの決定アルゴリズムはそのまま判定アルゴリズムとして利用することができるのでPはNPに含まれる。
決定アルゴリズムの時点で速度が十分ある(任意の問題を多項式時間で決定できる)場合は決定アルゴリズムをそのまま証明検証アルゴリズムに流用することができる。決定アルゴリズムを使った検証では#cが不要になる。(前回エントリより)
よってNP ⊇ Pという包含関係が成り立つ。ただしこの包含関係が真部分集合であるかどうかは30年以上前からの重大な未解決問題(P ≠ NP予想)になっている。
Pが見つかっていないNPとNP完全
NPである問題に多項式時間アルゴリズムが見つかれば、その問題はPに分類することができる。
NP完全といわれるNP中の特殊なクラスの場合は少し話が違っていてPで解けるアルゴリズムが見つかった場合は全てのNP問題がPで解けるという、ある種革命的な状況が発生してしまう(P=NP)。
これ以外のNP問題、つまり現状でNP完全なのかPなのか分かっていない問題はNP-intermediateと言われている
ただしP=NPが判明すればNPIは空集合になる。P ≠ NPの場合はNPIが存在する。PapadimitriouのComputational Complexityにこのクラスの存在証明が乘っているらしい。
ぼくには簡単ではありませんが (^^;) Papadimitriou の Computational Complexity に証明が載っていました。対角線論法を使ってうまいこといったはず。
- 作者: Christos H. Papadimitriou
- 出版社/メーカー: Addison Wesley
- 発売日: 1993/11/30
- メディア: ペーパーバック
- 購入: 1人 クリック: 1回
- この商品を含むブログを見る
実際に本を確認してみたところ、以下の記述がそれらしい
Theorem 14.1: IF P ≠ NP, then there is a language in NP which is neither in P nor is it NP-complete(p330)
Theoremのあとに証明が続くが割愛
Papadimitriouの本以外にも以下の本にもNPIの章と証明はあった
Computational Complexity: A Modern Approach
- 作者: Sanjeev Arora,Boaz Barak
- 出版社/メーカー: Cambridge University Press
- 発売日: 2009/04/20
- メディア: ハードカバー
- クリック: 1回
- この商品を含むブログを見る
どの本に乗っている証明も以下の論文の引用になっていた
- Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility".
素因数分解やグラフ同型問題が今の所、このクラスだろうと考えられている
ちなみに多くの専門家はP=NPではないと予想している。(2012年時点で126/152人)
http://dopal.cs.uec.ac.jp/okamotoy/PDF/2013/complexity10confusions.pdf
