問題を解く鍵はアルゴリズムと時間計算量だ! 20世紀、急速に進化・発展したコンピュータの世界。コンピュータに計算させるためのプログラム、その基になるアルゴリズムの理論が誕生した。アルゴリズム、そして計算量の理論から生まれた多項式時間(P)で解けるとは。そして、非決定性多項式時間(NP)で解けるとはどういうことか。100万ドルが懸ったミレニアム問題、未解決の「P≠NP」問題に迫ります! まえがき 私は東京大学理学部数学科で修士課程まで、純粋数学を勉強してから、電電公社(現NTT)の研究所に就職し、情報科学に転向した。その後、東大教養学部に戻った頃から、アルゴリズムの理論(計算量の理論、第3章で解説する)が急速に拡がり、発展途上の分野の研究に参加できたのは、ありがたいことであった。 しかし私はどちらかというと、たとえば「データを小さい順に並べ替える」というような「実用性がある、理論的にはやさし
![現代数学の超難問「P≠NP」問題とはなんだろう(野﨑 昭弘)](https://cdn-ak-scissors.b.st-hatena.com/image/square/5e549969beab5b4d98722ec51f2085ea5e026e8f/height=288;version=1;width=512/https%3A%2F%2Fgendai-m.ismcdn.jp%2Fmwimgs%2Ff%2F5%2F1200m%2Fimg_f5cfad74bdce2f26a7f60ec496d41b31157863.jpg)