多項式時間とは、アルゴリズムの計算の複雑さの尺度を指します。これに関連して、問題を解決するために必要なステップまたは操作の数が入力サイズ（n）の多項式関数として表現できる速度で成長する場合、アルゴリズムは多項式時間の複雑さを持っていると言われています。

たとえば、アルゴリズムの時間の複雑さがo（n^2）またはo（n^3）の場合、ステップの成長速度は正方形または立方体に比例するため、多項式時間の複雑さがあると見なされます。それぞれ入力サイズ。

入力サイズの増加に伴い、実行時間が比較的ゆっくりと成長するため、多項式時間アルゴリズムは一般に効率的と見なされます。対照的に、指数関数的な時間の複雑さ（たとえば、O（2^n）またはO（n！））を備えたアルゴリズムは、通常、入力サイズで非常に急速に成長し、大規模な問題に対して実用的でないため、非効率的ではないと見なされます。

複雑さ理論の文脈では、多項式時間における決定論的チューリングマシン（計算の標準モデル）によって解決できる問題は、複雑さのクラスPで分類されますが、非決定的なチューリングマシンによって解決できる決定問題多項式時間は、複雑なクラスNPに分類されます。多項式時間は、アルゴリズムの効率とコンピューターサイエンスにおける問題の牽引可能性について議論する際の重要な概念です。
Polynomial time refers to a measure of the computational complexity of an algorithm. In this context, an algorithm is said to have a polynomial time complexity if the number of steps or operations required to solve a problem grows at a rate that can be expressed as a polynomial function of the input size (n).

For example, if the time complexity of an algorithm is O(n^2) or O(n^3), then it is considered to have a polynomial time complexity because the growth rate of the steps is proportional to the square or cube of the input size, respectively.

Polynomial time algorithms are generally considered efficient, as their running time grows relatively slowly with the increase in input size. In contrast, algorithms with exponential time complexity (e.g., O(2^n) or O(n!)) are usually considered inefficient, as their running time grows very quickly with the input size, making them impractical for large-scale problems.

In the context of complexity theory, problems that can be solved by a deterministic Turing machine (a standard model of computation) in polynomial time are classified in the complexity class P, while decision problems that can be solved by a non-deterministic Turing machine in polynomial time are classified in the complexity class NP. Polynomial time is an important concept when discussing the efficiency of algorithms and the tractability of problems in computer science.