計算機科学者の間で“うまく解ける”問題とは，問題の規模が１０倍になっても，１００倍ないし１０００倍程度の時間をかければ解ける問題のことをいう。このような問題は，規模が１００倍になれば計算量は１万倍以上になるが，計算機が１０万倍速くなればたちどころに解ける。
ところが，ごく当たり前の問題の中に，問題の規模が１０倍になると，どのように工夫しても，２^10倍＝１０００倍の計算量が必要になると思われる，厄介な問題が存在することが明らかになったのである。
規模が１００倍なら計算量は２^100倍，すなわち１０^30倍になる。計算機が１００万（１０^6）倍速くなっても，このような問題を普通のやり方で解こうとすると何兆年もかかる。しかも世の中は，このような“うまく解けない問題”，すなわち「NP困難問題」が溢れているというのである。
この結果，わが国でも７０年代に入ると，難しい問題を解くためのアルゴリズムや，ソフトウェア研究の重要性が認識されるようになった。京都大学，大阪大学，東京工業大学などの有力大学に，情報科学科・情報工学科・計算機科学科が出来たのはこの頃である。
しかしどの大学も，その規模は一学科分（教官定員１５人，学生定員４０人程度）で，米国の有力大学に匹敵する“ソフトウェア中心の”計算機科学科は，どこにもなかった。政府・産業界・学界は，依然としてソフトウェアを軽視していたのである。
今野 浩 (2012). 工学部ヒラノ助教授の敗戦：日本のソフトウェアはなぜ敗れたのか 青土社 pp.16-17
PR
