ここんとこ「さんすうのはなし」が続いてるのでついでに。
「ゲーデルの不完全定理」と共に計算機科学と密接に関わるのが「P≠NP? 問題」です。
計算して何かをもとめるのが計算機のお仕事のひとつなわけです。
計算には"簡単な計算"と"難しい計算"があります。
たとえばN個のデータが並んだ中から特定のデータを検索する。
これはアタマからケツまでだーーーーっと調べりゃいいから計算時間はNに比例します。
x == y であるx,y をN個のデータから探しだす。
N個のデータ中からふたっつ取り出す組み合わせを全部試せばいいんで
計算時間はN^2に比例しますな。
...ま、こんなスンポーで計算時間や必要メモリ量が"データ数のなんとか乗"に
比例する程度の計算は"簡単な計算"に属します。
# 'なんとか'がどんなに大きくても ^^;
一方データ数のなんとか乗では収まらない計算もたーくさんあるです。
"データ数の階乗" や "2のデータ数乗" に比例する時間がかかっちゃうとかね。
こっちに属するやつはデータ数が多くなると正面からはとても解けたもんじゃない、
一万年と二千年前から回してるうぅぅ(←ここで弾幕!)
八千年過ぎたあたりで諦めますふつー
簡単な計算─"データ数のなんとか乗"程度の問題を
データ数の多項式(Plynomial)のオーダーで求まることから P問題 と呼び、
そんなんじゃとてもじゃないが答えの出ない問題を NP問題 と呼んでます。
で、NP問題はホントにNP問題なんだろうか?
うまいアルゴリズムが思いつかないだけで、
ホントは多項式オーダーで求まる(=P問題)んじゃなかろーか?
計算機屋さんたちは手に負えないNP問題を解きたくて仕方がない。
面白いことにNPに属する問題のどれかひとつでいいから多項式オーダー
で解くことができれば、他のすべてのNP問題も多項式オーダーで解けるって
ことが証明されています。けども未だかつてNP問題を多項式オーダーで
解けたためしがありません。"原理的に解けないんじゃないのかぁ?"ってわけ。
"原理的に解けない"ことが証明されればあきらめがつく(=肩の荷がおりる)わけだし、
その反例が一個見つかったんならすべてのNP問題が多項式オーダーで解けるんだからみんな大喜び♪
P≠NP? 未だ解けぬ難問です。