◆計算量理論◆

膨大な計算量の解決を目指す学問

数学的に記述されたある問題を解くのに、どのくらい時間がかかるかに関する数学・コンピュータ科学の理論を、計算量理論という。

あるコンピュータプログラムが理論的には実行可能であったとしても、その完了に何百年もかかるとしたら、計算結果を得ることはできないだろう。例えば、複数の地点を回るための最小の時間を計算する問題（巡回セールスマン問題）は、現実的な時間では計算できない計算量になることが知られている。

【情報学基礎理論】分野では、プログラミングや、計算を解くための手順（アルゴリズム）についての基礎研究を行っており、計算量理論も扱う。

現実の問題を数学的に表してそれを解こうとする【数理情報学】では、現実的な時間で終わるような計算量を追求する。