Apr 25, 2017
(「P≠NP」問題 現代数学の超難問 (ブルーバックス) | 野崎 昭弘 |本 | 通販 | Amazonから)
この本は、「コンピュータ科学」の教養として、 最後に「P!=NP問題」へ至る構成となっている。 たとえば、「ネーピアの棒」とか「ソフトウェア」の語源とか 「ネヴァリンナ賞」のような話が散りばめられている。
たぶん著者がいちばん言いたいことだろうが、 「NP問題」のNは"Non-deterministic"のことで、つまり非決定性多項式問題である。 分岐に対して非決定に同時進行できれば多項式時間に収まる問題である。 もしくは、(偶然に)すべて分岐で正解ルートを辿れていれば、 多項式時間で終わる問題ともいえる。 決定性にやる場合には、正しいルートにあたるまで、 戻って選び直して正しくないルートをたくさん通るので、 指数時間かかることになる。 NP問題は、一般的な意味での指数問題の一領域として区別する。
充足問題(SAT)では、解く論理式にある命題変数全部を並べて、 そこにtrue/falseを入れて、その論理式全体を計算してtrueかfalseかを出せる。 変数列のtrue/falseの1パターンに対しての論理式全体の計算は多項式時間であるが、 変数列の全falseから全trueまでの全パターンでは、変数がN個あれば、 2のN乗個のパターンになるので、指数回の計算になってしまう。
著者は最後でN=NP問題に重要性はないと結論しているが、 現在bitcoinのマイニングはNP問題の特性を活用しているのではないか。 正解のnonceならハッシュ値をすぐ検証できるが、 正解のnonceを見つけるのに大量の計算を行わせている。