NPクラスのNondeterministic polynominal algorithmについて
4部作その3。組合せ最適化のページ(p422~423)の理解メモです。100回くらい同じページを読んだ結果、本書の記述だけだと不十分に感じたの類書を参考にしています｡
- 作者: B.コルテ,J.フィーゲン,浅野孝夫,浅野泰仁,小野孝男,平田富夫
- 出版社/メーカー: 丸善出版
- 発売日: 2012/02/29
- メディア: 単行本
- クリック: 5回
- この商品を含むブログ (1件) を見る
余談:NP(Nondeterministic polynominal)という特性
※重要だと思って精読しましたが、乱択アルゴリズムを考えないときはあまり重要ではないので個人の判断で読み飛ばしてください。本書でもnon-deterministic polynominalを何かの前提・準備として紹介していません。
NPで扱える決定問題の種類はdeterministicに限らない。NPのNondeterministicという名前は決定問題のアルゴリズムとして採用できるアルゴリズムの制約からきている。
以下は同値である。
非決定性アルゴリズムはランダム化アルゴリズム(randomized algorithm)の一種。
ランダム化アルゴリズムはf(s)→Tに対して以下のものと定義されています。
- 関数g:{s#r:s∈S,r∈{0,1}k(s)}→T
ランダム化アルゴリズムはある問題f(s)インスタンスのサイズに依存する多項式時間個のランダムビットrを使って元のアルゴリズムと近い決定ができるアルゴリズムです。元のアルゴリズムとどの程度精度が一致しているかで以下のように分類されています。
| algorithm | definition (※全てp422からの抜粋) |
|---|---|
| モンテカルロアルゴリズム | インスタンスによらず少なくとも正の確率pで正しい答えを出力する |
| 片側誤差のあるランダム化アルゴリズム | f(s)=0となるどのs∈Sに対しても、全てのr∈{0,1}k(s)でg(s#r)=0となる |
| 非決定性アルゴリズム | f(s)=1となる各s∈Sに対してg(s#r)=1を満たすr∈{0,1}k(s)が少なくとも1個存在する |
| ラスベガスアルゴリズム | すべてのs∈Sに対してg(s#r)=f(s)である理想的な場合 |
下図のような閉包関係があります。
ここまで読んでまともな人ならお気付きかと思いますが、非決定性アルゴリズムの
f(s)=1となる各s∈Sに対してg(s#r)=1を満たすr∈{0,1}k(s)が少なくとも1個存在する
インスタンスによらず少なくとも正の確率pで正しい答えを出力する
という特性がすでに満たしているように読めるはずです。すなわち本書の記述のみを頼りに考えると「片側誤差のあるランダム化アルゴリズム」と「非決定性アルゴリズム」の集合のサイズは完全一致になるはずです。
本棚があったので類書を少し調査してみました。
乱択アルゴリズム (アルゴリズム・サイエンス・シリーズ―数理技法編)
- 作者: 玉木久夫
- 出版社/メーカー: 共立出版
- 発売日: 2008/08/08
- メディア: ハードカバー
- 購入: 4人 クリック: 52回
- この商品を含むブログ (8件) を見る
すると、この本のp12を読むと片側誤差のあるランダム化アルゴリズムについて興味深いことがわかりました。
乱数の出方に寄らず常に正しい結果を与える乱択アルゴリズムをラスベガスアルゴリズム(Las Vegas algorithm)と呼ぶ。これに対して、乱数の出方によって誤った結果を与えることが実際にあるアルゴリズムをモンテカルロアルゴリズム(Monte Carlo algorithm)と呼ぶ。(中略) 対象とする問題が、判定問題(decision problem),つまりYESかNOと答えるタイプの問題である場合、モンテカルロアルゴリズムはさらに、片側謝りアルゴリズム(one-sideed error algorithm)と両側謝りアルゴリズム(both-sided error algorithm)の二つに分類される。真の答えがYESの時だけ、あるいはNOの時だけ誤る可能性があり、反対の場合には必ず正しく答えるアルゴリズムは片側誤りアルゴリズムである。どちらの場合にも誤る可能性のあるアルゴリズムは両側誤りアルゴリズムである。
黄色い本と白い本のone-sided error algorithm(片側謝りアルゴリズム、片側誤差のあるランダム化アルゴリズム )について定義を比較してみましょう
| 本 | 定義 |
|---|---|
| 黄色い本 | f(s)=0となるどのs∈Sに対しても、全てのr∈{01}k(s)でg(s#r)=0となる |
| 白い本 | YESあるいはNOの時だけ誤る可能性があり、反対の場合には必ず正しく答える |
白い本のone-sided error algorithmの定義がより厳密と仮定すると、片側誤差ありアルゴリズムはYESインスタンスまたはNOインスタンスのどちらかは正しく決定することができるアルゴリズムということになります。黄色い本は"YES sideに誤差がありNo sideは完璧に答えるアルゴリズム"を暗黙の前提にしています。
上記を踏まえて乱択アルゴリズムの表は次のように再構成できます。
| algorithm | definition (※全てp422からの抜粋) |
|---|---|
| モンテカルロアルゴリズム | インスタンスによらず少なくとも正の確率pで正しい答えを出力する |
| 片側誤差のあるランダム化アルゴリズム | YESインスタンスもしくはNoインスタンスのどちらかを完全に正しく決定できる |
| 非決定性アルゴリズム | NOインスタンスを正しく決定できる |
| ラスベガスアルゴリズム | すべてのs∈Sに対してg(s#r)=f(s)である理想的な場合 |
上記の分類は黄色、白い本の内容と矛盾なく乱択アルゴリズムをうまく分類できているように思えますが、専門家ではないのですこし自信がありません。*1
非決定性アルゴリズムが存在する↔︎クラスNP なのはなぜか
証明をそのまま載せてしまうのはアレなので概略だけさっと書きます。ランダムビットrをcertificateと読み替えて、ランダム化アルゴリズムをそのまま証明検証アルゴリズムに置き換えることが出来ます。
非決定性アルゴリズムの定義
f(s)=1となる各s∈Sに対してg(s#r)=1を満たすr∈{0,1}k(s)が少なくとも1個存在する
から、NP問題の定義
任意のyes-インスタンスに対してのみ多項式時間で検証できる証明の存在だけが要求される。
補足:検証アルゴリズムの定義 Y = {y∈X:y#c∈Y'であるようなc∈{0,1}[p(size(y))]が存在する}
を導くことが出来ます。
補足情報
具体例としては以下の資料で2-SATをランダム化アルゴリズムを使って解く方法が挙げられています。
http://www-imai.is.s.u-tokyo.ac.jp/seminar/reading/resume/02summer_11.pdf
若干この本ではnondeterministicの話はわかりにくかったので、アルゴリズムイントロダクションという本を参照したところ、NP問題の特にnondeterministic側の問題に焦点を当てた本として以下のものが提示されていた。
アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書
- 作者: Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson
- 出版社/メーカー: 近代科学社
- 発売日: 2018/01/09
- メディア: Kindle版
- この商品を含むブログ (4件) を見る
Hopcroft and Ullman [180] give a good presentation of NP-completeness in terms of nondeterministic models of computation.
- [180] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
- 作者: John E. Hopcroft,Rajeev Motwani,Jeffrey D. Ullman
- 出版社/メーカー: Pearson
- 発売日: 2013/10/03
- メディア: Kindle版
- この商品を含むブログを見る
和訳もあるようです
オートマトン言語理論 計算論〈1〉 (Information & Computing)
- 作者: J.ホップクロフト,J.ウルマン,R.モトワニ,John E. Hopcroft,Jeffrey D. Ullman,Rajeev Motwani,野崎昭弘,町田元,高橋正子,山崎秀記
- 出版社/メーカー: サイエンス社
- 発売日: 2003/04/01
- メディア: 単行本
- 購入: 1人 クリック: 172回
- この商品を含むブログ (19件) を見る
- 作者: ジョン・E・ホッブクロフト,R・モトワニ,J・D・ウルマン,野崎昭弘,高橋正子,町田元,山崎秀記
- 出版社/メーカー: サイエンス社
- 発売日: 2003/08/13
- メディア: 単行本
- 購入: 3人 クリック: 22回
- この商品を含むブログ (11件) を見る
note:本エントリでは深入りしませんが、非決定性アルゴリズムより広い乱択アルゴリズムを考えたときの計算クラスもあるようです。
