ある問題があり、それがNというサイズであるとします。この問題を「何ステップで解けますか？」ということが、問題の難しさを決めています。

理論計算機科学では、ある問題がNというサイズに関する多項式で解けるか、解けないかということが、たいへん重要なことなんですね。たとえば多項式Nの10乗といった数であれば、指数（10）のところがNに依存しないので、それほど大きな数にはなりません。一方、2のN乗という数になると、飛躍的に増大してしまう。試しにNに100を入れてみてください。理論計算機科学では、多項式解でとけないものは、どんなにがんばっても絶対に動かせない、つまりプログラムとして走らせることができないんです。

一般に、多項式時間で判定可能な問題群をPと呼んでいます。昔から数学的な大きな未解決問題として知られている、P＝NP？問題は、これを扱ったものです。しかしながら実装を考えると、Nに関して線形時間で解ける、またはN　×　Nに関する対数を用いたアルゴリズムや計算が、今日的なターゲットだと言えるでしょう。もしP＝NP？問題が解けたとしても、それが現実のアルゴリズムに何かインパクトを与えるというわけではないんですね。