Origin of the phrase 'in polynomial time'

Question

What is the origin and context of the phrase 'solvable in polynomial time' in computer science? Are they related to the notion of 'polynomials' in mathematics?

Answer 1

It describes that an algorithm can solve a problem in polynomial time for a given input size. This phrase is a result of the so called bigO notation. Just look it up. It is a part of complexity theory in computer science.

In practice you can assume that the runtime of a polynomial time algorithm is still practical even for larger input sizes. In contrast, exponential time algorithms take a lot of longer, even for small input sizes since the exponential function increases very fast.

Answer 2

In complexity theory, we talk about algorithms in terms of the functions that describe their run time. If we let $n$ be the number of variables and assert that an algorithm runs in "$f(n)$ time," what we mean is that the function that describes the runtime of the algorithm (modulo certain standard assumptions and generalizations), grows similarly to $f(n)$ in the sense that their ratios has a finite limit as $n\to\infty$.

We define a problem to be solvable in polynomial time if there exists an algorithm that solves the problem such that the algorithm runs in polynomial time. Equivalently, we might say that the algorithm is $O(n^c)$ for some $c$ where $O(x)$ is Big-O Notation

Answer 3

If the number of steps needed to solve a problem of size n is bounded by some polynomial $f(n)$, then it is said to be solvable in polynomial time. So an example of this might be sorting a list of numbers. If we have $n$ different numbers, then the number of steps needed to sort the list would be bounded by $f(n) = n^2$. You may have tighter bounds such as $f(n) = \frac{n(n+1)}{2}$ but when we're talking about run-times of algorithms, we basically ignore all constants and lower order terms.

Answer 4

The emphasis on polynomial time as proxy for practical algorithms was put forward and popularized by Edmonds, though it first appeared in Cobham, and is now sometimes called the Cobham–Edmonds thesis.