蛍光ペンの交差点

"科学と技術に支えられ、夢を語る人になる"

MP-hard (Measuring is practically hard) な問題

コンピューターサイエンスの分野には、NP-hard(エヌピー・ハード)と呼ばれる問題群が存在する。雑に言えばその問題集合に含まれる問題にはある種の困難性が付きまとい、扱う対象の数が増えるに連れてすぐにまともに計算が追いつかなくなるというものだ。宇宙が始まってから計算していたとしてもまだ終わっていない、その手の計算問題が世の中にはたくさんある。

 

この話はコンピューターサイエンスのカリキュラムで出てくるのだが、
ふと、そのアイデアをデータサイエンスの文脈で考えることはできるだろうか、と疑問に思った。

 

計算量とは、計算にかかる手数(ステップ数)を大まかに調べるための道具である。そしてデータサイエンスにおける基礎的な計算として、調べたいものの状態を数値で測るというものがある。測った数値のことを一般的にMetrics(メトリクス)と呼ぶ。

 

現代の人々は多様なものを測りたがる。

 

飛行機のメーカーごとの内燃機関の平均回転数、ウガンダにおける紛争による傷病度別の負傷者、大統領がA国の諜報員と過去2年間で何度接触したかの相手別回数統計、採取された1億個の細胞の中で変異が確認できる割合、GDPが昨年と比べてどの程度向上したか、産業別ではどうか、地域別ではどうか、都道府県ではどうか、市町村ではどうか、各企業ではどうか、各社員ではどうか、各社員の1ヶ月の貢献割合ではどうか、各社員の1時間ごとの貢献割合ではどうか、中途社員と新入社員別ではどうか、勤続年数5年以下とそれ以外ではどうか。

 

こうやって一つの物事をどこまで細かく測れるかを追求していくと、小学生ぐらいのときに全てを書きつけようとして結局何も書けなかったノートのことを思い出す。取得して保存して計算するまでの手数が多すぎるという困難性が付きまとうのだ。

 

このような現象を、NP-hardに倣ってMP-hardと呼ぶことに意義はあるだろうか。計算量は一つだけ定義してもそれほど役立たず、他の計算量クラスとの関わりで全体像が掴みやすくなる。PをPractical(現実的でほぼ確実に計算できる)などだろうか。などという取り留めのない発想であった。