この数十年でコンピュータの性能が飛躍的に向上したおかげで、多種多様な問題をコンピュータ上で扱えるようになりました。みなさんが普段使っているウェブサービスでも、後ろで様々な計算が行われています。例えば、地図アプリで目的地までの道順を調べるとすぐに最適な経路を教えてくれます。他にも、検索サービスで調べたいことを入力すると、上から順に関連がありそうなウェブサイトを表示してくれます。こういったサービスでは、地図のデータやウェブページのデータといった巨大なデータの中から、私たちが知りたい情報を一瞬で導き出して教えてくれます。このようにコンピュータで答えを高速に計算できる問題がある一方で、どのような計算方法（アルゴリズム）を考えても、正しい答えを求めるのに膨大な時間がかかってしまう（と信じられている）問題があります。例えば、素因数分解といった、数学でおなじみの問題は、今のコンピュータでは簡単に答えを求めることができない代表的な問題の一つです。こういった計算が難しい問題は、その計算の難しさを利用して、解読が困難な暗号の設計などに応用されています。この講義では、アルゴリズム理論や計算量理論とった分野で、様々な問題の計算の難しさがどのように解明されてきたかについて話します。

平石 秀史