« 予想外の反応に一喜一憂するブロガー達 | トップページ | 過去ログを読ませるための方法 »

プログラムの品質とP≠NP予想

私も、入社してから7年目。気がつけば、プログラムをゴリゴリ書く側から、管理する側になろうとしています。年々、効率化と高品質化を求められるのはどの開発現場でも同じでしょうが、私の職場では何よりバグを出さないことが最重要視されるので、今年初めてリリース後バグを出してしまったときはだいぶヘコみました(現状影響なしと判断され即日改修にはなりませんでしたが←苦しい言い訳)

さて、今回は数学のお話。世の中には「ミレニアム懸賞問題」というこの問題を解いたら1億円!という超難問が存在します。その一つ、P≠NP予想にちょっと触れてみようと思います。厳密に説明するのは難しいので簡単に説明すると、P問題とは「多項式時間での解法が存在する問題」のことで、NP問題とは「答えが与えられた時に、その答えが正しいかどうかを多項式時間で判定できる問題」のことです。このとき、P⊂NPであることは自明ですが、P⊃NPはどうだろうか?という問題です。多くの学者達はこれは成り立たないと思っているため「P≠NP予想」と呼ばれているのです。

と、こんな説明で分かるわけねーよとか言われそうですが、要するにP=NPとは「どんな問題にも一般的な解法がある」ことで、P≠NPとは「世の中には、総当たりでしらみつぶしに調べる以外に解法が存在しない問題が存在する」ことである。P≠NPであるだろうという予想から、暗号の世界でこのように活用されています(RSA暗号)。例えば、816256193を素因数分解しろと言われたらどうします?私には小さい素数からしらみつぶしに調べることしか思いつきません。しかし、816256193=26981×30253であると答えを示されたら、これを証明するのは非常にカンタンですね。この答えを探すためにしらみつぶしに探すしかないことを証明するか、あるいはすべての問題に対し何かしら一般的な解法を用いて答えを導くことができることを証明することができれば、1億円がもらえるのです。

というわけで、やっとプログラムの話に戻りますが、ここに何かしらバグが存在するプログラムが存在します。このプログラムからバグを見つけ出す一般的な方法ってあるでしょうか?そんなことを考えたら、これってP≠NP予想に似てる!と思ったわけです。バグ入りプログラムからバグを見つけるのと、バグの箇所を指摘されてその指摘箇所が本当にバグかどうかを確かめるのとでは、どちらが簡単か、なんて言い換えられるかな?機械的な確認だけですべてのバグを取れるだろうか。すべてのバグを取ることができる確認ツールを作ることは可能だろうか。これもP≠NP予想同様、不可能だと思うのです。

プロジェクトの成功も品質レベルも、私は人に依存するものだと考えていて、小規模プロジェクトでは開発者に、大規模プロジェクトでは管理者に依存すると思っています。数百人以上のプロジェクトしか経験のない私ですが、管理者だけでなくシステムにも依存するでしょうか。多くの人が出入りするために、業務や開発の知識がない人でも良い品質でプログラムを作ることができるシステムがどこまで整っているかが重要だと思うのです。優秀なレビュアがすべてチェックすればほとんどのバグは取れるでしょう。しかし、それでは効率どころの話ではありません。どんな人でもあるステップを踏めばすべてのバグが取れるようなシステム、これを考えたら1億円どころの騒ぎではありませんね。

こんな感じで、会社では効率化と高品質化の間で頭を悩ませる日々を送っています。

P≠NP予想については、容疑者Xの献身というミステリー小説(?)で知ったのをきっかけに自分でも調べてみました。この本の中ではP≠NP予想を「自分で考えて答えを出すのと、他人から聞いた答えが正しいかどうかを確かめるのとでは、どちらが簡単か」という表現で使っています。おもしろい本でしたので興味がありましたら読んでみてはどうでしょう。

容疑者Xの献身
容疑者Xの献身
posted with amazlet on 06.07.26
東野 圭吾
文藝春秋 (2005/08/25)
売り上げランキング: 262

はてなブックマークに追加
はてなブックマークのコメントを参照

|

« 予想外の反応に一喜一憂するブロガー達 | トップページ | 過去ログを読ませるための方法 »

コメント

「プログラムからバグを見つけ出す一般的な方法」を PNP に関連付けるのは間違っています.これは「チューリングマシンの停止性問題」であって,不可能であることが厳密に証明されています.PNP をうんぬんする以前に計算可能(computable)ですらありません.ちなみにゲーデルの不完全性定理と全く同じ問題でもあります.

投稿: anonymous | 2006.08.21 20:21

通りすがりの者です。
TVで天才数学者が出て来るドラマがありまして
そのドラマの中で『P not NP 問題』なる台詞が登場しまして
調べてみましたが『Wikipedia』の内容では『全く理解出来ず....汗』
こちらの記事でようやく『モヤモヤ』がスッキリしました。
これでスッキリ眠れます..笑(小さい悩みですみません...アハハ)
THANKS!

投稿: smile? | 2007.01.29 22:48

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/1573/11110666

この記事へのトラックバック一覧です: プログラムの品質とP≠NP予想:

« 予想外の反応に一喜一憂するブロガー達 | トップページ | 過去ログを読ませるための方法 »