巡回セールスマン問題やスケジューリング問題などに代表されるよう， 我々が実社会で遭遇する離散最適化問題の多くは， 最適な解を効率よく見つけることができない問題と見なされている． （これがＰ≠ＮＰ予想である．） このような計算困難性に対処するために， 最適解に近い解（近似解）を求めるアルゴリズム， 近似アルゴリズム の研究がなされている． ＮＰ困難な最適化問題の中には， 任意の良い近似精度を保証した効率のよいアルゴリズムが示された問題も数多く存在する． その一方で， 確率的検査可能証明 におけるＰＣＰ定理を使うことにより， （Ｐ≠ＮＰという仮定のもと）近似不可能であることが示された問題も数多く存在する． このようなＮＰ困難性や近似困難性は， 「すべての」入力を効率よく解くことができるわけではないという 「最悪時」の計算困難性である． 平均時解析とは， このような「最悪時計算量」とは対照的に， 問題の平均的な解きやすさ，「平均時計算量」，を解析する研究分野である． （問題の平均的な「解きにくさ」を研究する分野もある．）
以下のような代表的なＮＰ困難な問題に対して， 平均的に効率よく解くアルゴリズムが示されている：
では，どのようにして問題の平均的な解きやすさが示されているのだろうか？ ここでは， [1] で示された頂点彩色問題を例にとって解説する． そこでは，次のような問題を扱っている． 頂点３彩色可能なグラフが入力として与えられて， その頂点３彩色の一つを出力する． 入力となる例題の分布は次のように定義される： まず，頂点を３等分割する． 異なる分割の任意の頂点対に辺を確率 p ではる． このようにして生成されるグラフが入力として与えられる． （明らかに，入力として与えられるグラフは頂点３彩色可能である．） [1] では， この分布に対して「平均的に」効率よく解くアルゴリズムが提案されている． （正確には，「平均的に」ではなく「高い確率で」．） 具体的には， 与えられたグラフの行列の最小固有値に対応する固有ベクトル， 第二最小固有値に対応する固有ベクトルの二つのベクトルを用いてグラフの頂点を３分割する． （ベクトルの要素の大きさによって３分割する．） それをグラフの３彩色として出力する． こうして得られた頂点の３分割が（例題の分布に対して）高い確率で３彩色となる ことが（理論的に）示されている． つまり， 上で定義された例題の分布から生成されるグラフのほとんどは， このアルゴリズムで３彩色が求められることを意味している．
最初に述べたように， ＮＰ困難性や更には近似困難性が示された離散最適化問題が数多く存在する． これは， 「すべての」入力を効率よく解くことが難しいと思われれている問題である． よって， このような「最悪時」の計算困難性に対処するには， 問題を平均的に効率よく解くことを考える必要がある． 問題を平均的に効率よく解くアルゴリズムが， 実用的な問題を扱う産業界では特に重要となってくる． 対象としている問題の入力となる例題の分布を特徴付け， その分布に対して（平均的に）効率よく解くアルゴリズムを考案することで， 開発者の経験に基づいたヒューリスティックスや， ベンチマーク（だけ）によるプログラムの性能評価に， 確固たる理論的保証を与えることができる．