The phrase “polynomial time” is a way of separating algorithms whose running time grows at a controlled algebraic rate from algorithms whose running time explodes when the input length increases. This distinction matters most when the objects are finite but enormous: a graph with thousands of vertices, a code of length millions, a finite group given by generators, or an integer with hundreds of digits. In each case the raw set of possibilities may be too large to inspect, so the mathematical question becomes whether the structure of the problem can be exploited before exhaustive search takes over.

A first trap is to measure time in the wrong variable. Trial division tests whether an integer $N$ is prime by checking divisors up to roughly $\sqrt{N}$, which sounds moderate if $N$ itself is the input. But the input is not $N$ unary marks; it is usually the binary expansion of $N$, whose length is about $\log_2 N$. An algorithm taking $\sqrt{N}$ steps is exponential in the number of input bits. Polynomial time is built to avoid this mistake: it measures running time as a polynomial in the length of the encoded input.

[example: Trial Division and Bit Length] Let $N$ be an odd integer written in binary, and let its input length be \begin{align*} n=\lfloor \log_2 N\rfloor+1. \end{align*} By the definition of the floor function, this means \begin{align*} n-1 \le \log_2 N < n. \end{align*} Exponentiating base $2$ gives \begin{align*} 2^{n-1} \le N < 2^n. \end{align*} In the worst case, trial division tests every odd integer $d$ with $3 \le d \le \sqrt{N}$. If $m=\lfloor \sqrt{N}\rfloor$, then the number of odd candidates is \begin{align*} \left\lceil \frac{m}{2}\right\rceil-1. \end{align*} Using $\lceil m/2\rceil \ge m/2$ and $m=\lfloor \sqrt{N}\rfloor \ge \sqrt{N}-1$, this number is at least \begin{align*} \frac{m}{2}-1 \ge \frac{\sqrt{N}-1}{2}-1=\frac{\sqrt{N}-3}{2}. \end{align*} Since $N \ge 2^{n-1}$, we also have \begin{align*} \sqrt{N} \ge \sqrt{2^{n-1}}=2^{(n-1)/2}. \end{align*} Therefore the number of candidates is at least \begin{align*} \frac{2^{(n-1)/2}-3}{2}. \end{align*} On the other hand, the number of tested divisors is at most $\sqrt{N}$, so it is bounded by a polynomial in $N$, for example by $N$. The same count grows like $2^{n/2}$ as a function of the bit length $n$, so trial division is polynomial in the numerical magnitude $N$ but not polynomial in the binary input length $n$. [/example]

This example explains why polynomial time is not just a slogan about speed. It is a statement about encoding, input size, and uniform control over all inputs of a given length. In algebra, this viewpoint turns qualitative existence theorems into effective questions: can we compute a greatest common divisor, solve a system of linear equations over a field, decode a code up to a promised number of errors, or decide a group-theoretic property without enumerating an exponentially large search space?

## Encoded Inputs and Running Time

Before defining polynomial time, the input model has to be fixed. Mathematical objects do not arrive inside an algorithm as abstract sets or rings; they arrive as finite strings over some finite list of symbols. The first piece of structure is therefore the finite symbol set from which all encoded inputs are built.

[definition: Alphabet] An alphabet is a finite nonempty set $\Sigma$. The set of finite strings over $\Sigma$ is denoted by $\Sigma^*$. [/definition]

An alphabet gives the universe of possible inputs, but it does not yet give the scale of an input. The next definition isolates the quantity that will replace informal phrases such as “the size of the number” or “the size of the matrix” in running-time statements.

[definition: Input Length] Let $\Sigma$ be an alphabet. The input length map is the function \begin{align*} |-|: \Sigma^* &\to \mathbb{N} \cup \{0\} \end{align*} with action \begin{align*} x &\mapsto |x|. \end{align*} Here $|x|$ is the number of symbols in the string $x$. [/definition]

Once inputs have lengths, a yes-or-no computational question can be treated as a set of accepted strings. This formulation is restrictive enough to support reductions and broad enough to encode many algebraic questions, such as whether a matrix is invertible or whether a polynomial has a root over a finite field.

[definition: Decision Problem] A decision problem over an alphabet $\Sigma$ is a subset $L \subset \Sigma^*$. An input $x \in \Sigma^*$ is accepted if $x \in L$ and rejected if $x \notin L$. [/definition]

Algorithms can be formalized using Turing machines, RAM machines, Boolean circuits, or other standard models. For polynomial time, the precise reasonable model does not change the class of decision problems, but a page needs one formal anchor. We use deterministic algorithms and measure the worst-case number of elementary steps.

[definition: Running Time] Let $A$ be a deterministic algorithm whose inputs lie in $\Sigma^*$. The running time of $A$ is the function $T_A: \mathbb{N} \to \mathbb{N} \cup \{0\}$ defined by \begin{align*} T_A(n) = \max\{\text{number of steps used by } A \text{ on input } x : x \in \Sigma^*,\ |x| = n\}. \end{align*} [/definition]

This worst-case convention asks for a uniform guarantee on all inputs of length $n$, not only on a typical input or a random input drawn from a convenient distribution. The next definition singles out the algorithms whose worst-case growth is bounded by a fixed power of input length.

## Definition

The preceding machinery now has a purpose: it lets us say that an algorithm remains usable as the input grows, with the input measured by the number of symbols actually supplied to the machine. The bound must be uniform across all strings of the same length, because a single difficult family of inputs is enough to defeat an alleged efficient method. Polynomial time captures this uniform scalability without insisting on a particular exponent in advance.

[definition: Polynomial-Time Algorithm] Let $A$ be a deterministic algorithm with inputs in $\Sigma^*$. The algorithm $A$ is a polynomial-time algorithm if there exist constants $C > 0$ and $k \in \mathbb{N} \cup \{0\}$ such that \begin{align*} T_A(n) \le C n^k \end{align*} for every $n \in \mathbb{N}$. [/definition]

The exponent $k$ and constant $C$ are allowed to depend on the algorithm, but not on the particular input of length $n$.

## Languages and Computable Functions

Since many algorithms can decide the same language, complexity theory usually classifies the problem rather than the particular code used to solve it. This matters because a slow algorithm for a language may coexist with a faster one, and the mathematical property we care about is whether any deterministic method solves all instances with polynomial worst-case growth. The class $P$ records exactly those decision problems for which such a method exists.