計算リソース

計算複雑性理論において、計算リソースとは、計算問題の解決においていくつかの計算モデルによって使用されるリソースです。

最も単純な計算リソースは、計算時間（問題を解決するために必要なステップ数）とメモリ空間（問題を解決している間に必要なストレージの量）ですが、これより複雑なリソースも数多く定義されています。^[要出典]

計算上の問題は、一般的に、有効な入力に対するその動作の観点から定義されます^{[要出典] 。問題の例としては、「整数}nが与えられた場合、n が素数かどうかを判定する」や「2 つの数値xとyが与えられた場合、積x * yを計算する」などがあります。入力が大きくなるにつれて、問題を解決するのに必要な計算リソースの量も増えます。したがって、問題を解決するのに必要なリソースは、リソースを入力の長さまたはサイズの関数として識別することにより、漸近解析の観点から説明されます。リソースの使用量は、多くの場合、 Big O 表記法を使用して部分的に定量化されます。

計算リソースは、どの問題が各計算リソースの一定量で計算できるかを研究できるため便利です。このようにして、問題を解決するためのアルゴリズムが最適かどうかを判断し、アルゴリズムの効率性について述べることができます。特定の計算リソースの一定量を使用して解決できるすべての計算問題の集合は複雑性クラスであり、異なる複雑性クラス間の関係は複雑性理論における最も重要なトピックの 1 つです。

「計算リソース」という用語は、アクセス可能なコンピューティング機器およびソフトウェアを説明するためによく使用されます。ユーティリティ コンピューティングを参照してください。

計算能力を正式に定量化する取り組みはいくつか行われてきました。境界付きチューリングマシンは、状態遷移の数とアルファベットのサイズを使用して特定の計算をモデル化し、特定の問題を解決するために必要な計算労力を定量化するために使用されてきました。^{[1] [2]}