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. [definition: The Class $P$] Let $\Sigma$ be a finite alphabet. A decision problem $L \subset \Sigma^*$ belongs to $P$ if there exists a polynomial-time deterministic algorithm $A$ such that, for every $x \in \Sigma^*$, the algorithm $A$ accepts $x$ if and only if $x \in L$. [/definition] This is a statement about the language $L$, not about a preferred implementation of an algorithm for $L$. Under the standard polynomial-simulation relationships among reasonable deterministic models of computation, the membership of $L$ in $P$ is model-invariant even though the exact running-time polynomial may change. In algebraic applications, many problems are not naturally yes-or-no questions. We may want to output a greatest common divisor, a basis for a kernel, or a shortest representative. To handle these tasks, the same time bound has to control the production of the output string. [definition: Polynomial-Time Computable Function] Let $\Sigma$ and $\Gamma$ be finite alphabets. A function $f: \Sigma^* \to \Gamma^*$ is polynomial-time computable if there exists an algorithm $A$ and constants $C > 0$, $k \in \mathbb{N} \cup \{0\}$ such that, on every input $x \in \Sigma^*$, the algorithm halts with output $f(x)$ after at most $C|x|^k$ steps. [/definition] For functions, the time bound forces $|f(x)|$ itself to be at most polynomial in $|x|$, since an algorithm needs time to write its output. This rules out hidden exponential output from being called efficient. ## Encodings and Algebraic Input Size ### Equivalent Encodings Polynomial time is only meaningful after choosing finite encodings for the mathematical objects. Algebra gives many compact descriptions: a finite field element may be stored as a residue class, a graph as an adjacency list, a group as a multiplication table or by generators, and a polynomial as dense or sparse coefficient data. Since reasonable encodings should not change the answer to an efficiency question, we need a way to compare two representations of the same objects. [definition: Polynomial-Time Equivalent Encodings] Let $\mathcal{C}$ be a class of finite mathematical objects. Two encodings $e_1: \mathcal{C} \to \Sigma^*$ and $e_2: \mathcal{C} \to \Gamma^*$ are polynomial-time equivalent if the functions $e_2 \circ e_1^{-1}: e_1(\mathcal{C}) \to e_2(\mathcal{C})$ and $e_1 \circ e_2^{-1}: e_2(\mathcal{C}) \to e_1(\mathcal{C})$ are polynomial-time computable on their domains. [/definition] These conversion maps are defined on the image sets of the encodings, not on every possible string. Throughout this page, such a map is treated as a promised-input computation on valid encodings, or equivalently as a total string function extended by sending malformed strings to a fixed rejection symbol. With that convention in place, the definition prevents artificial encodings from hiding hard work inside the input representation. [example: Dense and Sparse Polynomial Encoding] Let $\mathbb{Z}[x]$ denote the [polynomial ring](/page/Polynomial%20Ring) in one variable with integer coefficients. Consider $f \in \mathbb{Z}[x]$ written as \begin{align*} f(x)=\sum_{i=0}^d a_i x^i. \end{align*} A dense encoding stores the full list $(a_0,a_1,\dots,a_d)$, so it has one coefficient slot for each integer $i$ with $0 \le i \le d$. A sparse encoding stores only the pairs $(i,a_i)$ for which $a_i \ne 0$. For \begin{align*} f(x)=x^{2^n}+1, \end{align*} the only nonzero coefficients are \begin{align*} a_0=1 \quad \text{and} \quad a_{2^n}=1. \end{align*} Thus a sparse encoding stores the two pairs $(0,1)$ and $(2^n,1)$. The exponent $2^n$ has binary expansion $1$ followed by $n$ zeros, so its binary length is $n+1$; hence the sparse description has length bounded by a fixed polynomial in $n$. The dense encoding must list every coefficient from degree $0$ through degree $2^n$. The number of coefficient slots is therefore \begin{align*} 2^n-0+1=2^n+1. \end{align*} So the same polynomial has a sparse description of size polynomial in $n$, but a dense description with at least $2^n+1$ coefficient positions. An algorithm whose running time is polynomial in the dense length may therefore require time polynomial in $2^n+1$, which can be exponential in the sparse input length. [/example] This difference is not a technical nuisance; it changes the mathematical problem. Sparse polynomial factorisation, identity testing, and root questions are different complexity questions from their dense counterparts because the input can describe very high degrees compactly. ### Bit Complexity Integer inputs produce another common encoding issue. Arithmetic operations on integers are not constant-time operations when the integers are part of the input; their bit lengths contribute to the cost. Without accounting for the bits of the operands, an algorithm could appear efficient merely because it hides the work of carrying, comparing, multiplying, or dividing long binary strings inside a single arithmetic step. The standard bit model rules out that distortion by charging for elementary operations on the encoded integers themselves. [definition: Bit Complexity] The bit complexity of an algorithm on integer inputs is its running time measured in elementary operations on bits of the binary encodings of all input integers. [/definition] Bit complexity is the relevant model for number-theoretic algorithms, cryptography, and exact linear algebra over $\mathbb{Z}$ or $\mathbb{Q}$. It is stricter than counting additions, multiplications, or divisions as unit-cost operations independent of operand size. [example: Euclidean Algorithm as a Bit-Length Algorithm] Let $a,b \in \mathbb{Z}$ with $0<b\le a$, and let $n$ be the maximum of their binary lengths, so $a<2^n$ and $b<2^n$. In one Euclidean step write \begin{align*} a=qb+r \quad \text{with} \quad 0\le r<b. \end{align*} Then \begin{align*} d\mid a \text{ and } d\mid b \iff d\mid b \text{ and } d\mid a-qb \iff d\mid b \text{ and } d\mid r. \end{align*} Thus replacing $(a,b)$ by $(b,r)$ preserves the greatest common divisor. The number of divisions is linear in $n$. If $b\le a/2$, then after one step the first entry is $b\le a/2$. If $b>a/2$, then the quotient is $q=1$, because $b\le a<2b$, and the remainder is \begin{align*} r=a-b<a-a/2=a/2. \end{align*} So after at most two divisions, the first entry has become less than half of its previous value. After $2j$ divisions without termination, the first entry is a positive integer strictly less than \begin{align*} a/2^j. \end{align*} Since $a<2^n$, after $2n$ divisions it would be less than \begin{align*} 2^n/2^n=1, \end{align*} which is impossible for a positive integer. Hence the algorithm uses at most $2n$ divisions. During the algorithm, all entries are nonnegative remainders smaller than earlier entries, so every integer being divided has binary length at most $n$. Schoolbook division of two $n$-bit integers uses at most $n$ quotient-bit steps, and each step uses comparison and subtraction of $n$-bit integers, so one division costs at most a fixed polynomial in $n$. Multiplying this polynomial cost by the at most $2n$ divisions still gives a polynomial in $n$. Therefore computing $\gcd(a,b)$ is polynomial-time computable with respect to binary input length. [/example] The next theorem isolates a reusable guarantee for integer arithmetic: greatest common divisors can be computed within the bit-complexity standard. This matters because many later algebraic algorithms, from modular inverses to rational row reduction, use greatest common divisors as subroutines. Naming the polynomial-time guarantee lets those later algorithms cite the result rather than rechecking the bit complexity each time. [quotetheorem:7896] The theorem is one of the first places where algebra and complexity reinforce each other. A divisibility question that looks like it might require searching through many candidates is solved by the Euclidean structure of $\mathbb{Z}$. ## Closure Properties and Reductions ### Composition Polynomial time is useful because it behaves well under composition. If one efficient procedure calls another efficient procedure a polynomial number of times, the combined procedure remains efficient. This is the basic mechanism behind modular algorithm design, so it deserves a formal statement. [quotetheorem:6183] The important hidden point is output length. Since a polynomial-time algorithm cannot print an exponentially long intermediate string, feeding $f(x)$ into $g$ keeps the input length of the second computation polynomially bounded in $|x|$. ### Reductions Composition becomes a comparison tool when the first computation translates instances of one problem into instances of another. Instead of solving a new problem directly, we encode its inputs as inputs to a known problem and require the yes-or-no answer to be preserved. [definition: Polynomial-Time Many-One Reduction] Let $L \subset \Sigma^*$ and $M \subset \Gamma^*$ be decision problems. A polynomial-time many-one reduction from $L$ to $M$ is a polynomial-time computable function $r: \Sigma^* \to \Gamma^*$ such that, for every $x \in \Sigma^*$, \begin{align*} x \in L \iff r(x) \in M. \end{align*} When such a reduction exists, we write $L \le_p M$. [/definition] A reduction $L \le_p M$ says that $M$ is at least as hard as $L$ from the viewpoint of polynomial-time decision procedures. The useful point is not only comparative hardness: if an input for $L$ can be translated efficiently into an input for $M$, then any efficient decision procedure for $M$ can be pulled back to one for $L$. This is the closure principle that makes reductions transfer polynomial-time solvability as well as lower-bound evidence. The next structural question is whether this pullback remains inside polynomial time after the translation step is composed with the decision procedure for $M$. The answer is what makes many-one reductions usable in practice: polynomial-time computability is stable under the composition needed to turn an algorithm for $M$ into an algorithm for $L$. [quotetheorem:6184] This theorem explains why reductions appear throughout algebraic complexity. A normal-form problem for groups, a feasibility problem for polynomial equations, or a decoding problem for linear codes may be compared with a standard complete problem by a carefully designed encoding. [example: Graph Colouring Encoded as Polynomial Constraints] Let $G=(V,E)$ be a finite graph, and let $k$ contain three distinct roots of $T^3-1$. Denote these roots by $\mu_3(k)=\{\rho_1,\rho_2,\rho_3\}$. We encode the three colours by these three field elements and introduce one variable $x_v$ for each vertex $v\in V$. The equations \begin{align*} x_v^3-1=0 \quad \text{for each } v\in V \end{align*} force $x_v\in \mu_3(k)$, because their solutions are exactly the roots of $T^3-1$ in $k$. For an edge $\{u,v\}\in E$, suppose first that $x_u,x_v\in\mu_3(k)$. Since $x_u^3=1$ and $x_v^3=1$, we have \begin{align*} x_u^3-x_v^3=1-1=0. \end{align*} Factoring the difference of cubes gives \begin{align*} x_u^3-x_v^3=(x_u-x_v)(x_u^2+x_u x_v+x_v^2). \end{align*} If $x_u\ne x_v$, then $x_u-x_v\ne 0$, so the field cancellation law gives \begin{align*} x_u^2+x_u x_v+x_v^2=0. \end{align*} Conversely, if $x_u=x_v=\rho$ for some $\rho\in\mu_3(k)$, then \begin{align*} x_u^2+x_u x_v+x_v^2=\rho^2+\rho^2+\rho^2=3\rho^2. \end{align*} The existence of three distinct roots of $T^3-1$ implies $\operatorname{char}(k)\ne 3$, since in characteristic $3$ one has $T^3-1=(T-1)^3$. Also $\rho\ne 0$ because $\rho^3=1$. Hence $3\rho^2\ne 0$, so the edge equation fails when the two endpoint values are equal. Therefore the system \begin{align*} x_v^3-1=0 \quad \text{for all } v\in V \end{align*} together with \begin{align*} x_u^2+x_u x_v+x_v^2=0 \quad \text{for all } \{u,v\}\in E \end{align*} has a solution exactly when the vertices can be assigned three colours so that adjacent vertices receive different colours. The construction uses $|V|$ vertex equations, $|E|$ edge equations, and one variable per vertex, with all equations of degree at most $3$, so its encoded size is bounded by a polynomial in $|V|+|E|$. [/example] The point of the example is not that the resulting polynomial system is easier to solve. It shows how algebraic decision problems can encode combinatorial ones with only polynomial overhead, which is the essential language of reductions. ## Arithmetic Algorithms in Polynomial Time ### Euclidean and Polynomial Arithmetic Many of the most important polynomial-time algorithms in algebra are not based on brute force. They exploit identities, divisions with remainder, linear structure, or modular decompositions. The simplest family comes from arithmetic in Euclidean domains and fields. Polynomial multiplication and division are core subroutines, so the first theorem in this section records their polynomial-time behaviour under dense encoding. [quotetheorem:7897] The dense hypothesis matters: it makes the degree part of the visible input. The coefficient hypothesis matters just as much. A long polynomial computation performs many field operations, so it is not enough for each operation to halt quickly on its two immediate inputs; the encodings of coefficients produced throughout the computation must remain polynomially bounded across the whole polynomial-length sequence of operations. With sparse inputs, multiplication can still be carried out on listed terms, but division and factorisation may behave in more delicate ways because cancellations and degree gaps carry information compactly. [example: Polynomial GCD over a Field] Let $k$ be a field with polynomial-time arithmetic and uniform polynomial control on coefficient-encoding growth during polynomially many operations. Let $f,g \in k[x]$ be given by dense coefficient lists, and first swap them if necessary so that $\deg f \ge \deg g$; this swap does not change their common divisors. At one Euclidean step with second entry nonzero, polynomial division gives polynomials $q,r \in k[x]$ such that \begin{align*} f=qg+r \end{align*} with either $r=0$ or $\deg r<\deg g$. This replacement preserves the greatest common divisor. Indeed, if $h$ divides both $f$ and $g$, then $h$ divides $qg$, so $h$ divides \begin{align*} r=f-qg. \end{align*} Conversely, if $h$ divides both $g$ and $r$, then $h$ divides $qg$ and hence divides \begin{align*} f=qg+r. \end{align*} Thus the pairs $(f,g)$ and $(g,r)$ have exactly the same common divisors, so they have the same monic greatest common divisor. Write the successive pairs as $(f_i,g_i)$, with \begin{align*} (f_{i+1},g_{i+1})=(g_i, f_i \bmod g_i). \end{align*} Whenever $g_{i+1}\ne 0$, the division condition gives \begin{align*} \deg g_{i+1}<\deg g_i. \end{align*} So the nonnegative integer $\deg g_i$ strictly decreases at every nonterminal step. Since the initial second degree is at most $\min\{\deg f,\deg g\}$ after the initial ordering, there can be at most $\min\{\deg f,\deg g\}+1$ divisions before the remainder becomes $0$. If the input length is $N$, then the dense lists have at most $N$ coefficient slots up to a fixed encoding convention, so the degrees are at most linear in $N$. By *Dense Polynomial Arithmetic over a Field is Polynomial Time*, each dense division costs polynomial time in the current dense lengths and coefficient-encoding lengths. The polynomial-control hypothesis ensures that all intermediate coefficient encodings produced during this polynomial number of divisions remain polynomially bounded in $N$. Therefore the total time is bounded by a polynomial in $N$, and the final nonzero remainder, made monic by one division by its leading coefficient, is $\gcd(f,g)$. [/example] ### Linear Algebra Linear algebra is the other central source of efficient algebraic algorithms. Gaussian elimination avoids enumerating possible solutions and instead transforms a system by invertible row operations. There is, however, a bit-complexity trap hidden inside this familiar method: row operations may create new field elements whose encodings are longer than the original entries. Before polynomial-time row reduction can be asserted over an encoded field, the encoding must control not only the cost of one arithmetic operation but also the size of intermediate elements produced by polynomially many such operations. [definition: Polynomially Controlled Field Encoding] Let $k$ be a field whose elements are encoded as strings over a finite alphabet $\Sigma$, and let $\operatorname{Elt}_k \subset \Sigma^*$ be the set of valid encoded field elements. Write $\operatorname{Elt}_k^\times \subset \operatorname{Elt}_k$ for the valid encodings of nonzero field elements. The encoding is polynomially controlled if the following string functions are polynomial-time computable: \begin{align*} \operatorname{eq}_k: \operatorname{Elt}_k \times \operatorname{Elt}_k &\to \{0,1\}, \end{align*} \begin{align*} \operatorname{zero}_k: \operatorname{Elt}_k &\to \{0,1\}, \end{align*} \begin{align*} \operatorname{add}_k: \operatorname{Elt}_k \times \operatorname{Elt}_k &\to \operatorname{Elt}_k, \end{align*} \begin{align*} \operatorname{sub}_k: \operatorname{Elt}_k \times \operatorname{Elt}_k &\to \operatorname{Elt}_k, \end{align*} \begin{align*} \operatorname{mul}_k: \operatorname{Elt}_k \times \operatorname{Elt}_k &\to \operatorname{Elt}_k, \end{align*} \begin{align*} \operatorname{div}_k: \operatorname{Elt}_k \times \operatorname{Elt}_k^\times &\to \operatorname{Elt}_k, \end{align*} where these functions represent equality testing, zero testing, field addition, subtraction, multiplication, and division by a nonzero element. In addition, for every polynomial $p$ there is a polynomial $q$ such that every straight-line computation using at most $p(N)$ field operations on input field elements of total encoding length at most $N$ produces only intermediate and output field elements whose encodings have length at most $q(N)$. [/definition] This condition is automatic in many standard finite-field encodings, and rational linear algebra can be handled in polynomial bit complexity by using fraction-free or modular methods that keep coefficient growth under control. Without such a hypothesis, a statement about polynomial-time arithmetic over a field does not by itself imply polynomial-time linear algebra over that field. The next issue is that “linear algebra” is not a single output type. Row reduction may be used to return a rank, a determinant, a basis for a kernel, a basis for an image, or a solution vector with a failure symbol when no solution exists. To make later statements precise, we package these outputs as explicit string functions rather than relying on the informal phrase “do Gaussian elimination.” [definition: Polynomial-Time Linear Algebra over a Field] Let $k$ be a field equipped with a polynomially controlled field encoding, let $\Sigma$ be a finite alphabet used to encode elements of $k$, matrices over $k$, vectors over $k$, finite lists of vectors, integers, and a distinguished symbol $\bot$, and let $\operatorname{Elt}_k \subset \Sigma^*$, $\operatorname{Mat}_k(m,n) \subset \Sigma^*$, $\operatorname{Vec}_k(n) \subset \Sigma^*$, $\operatorname{Basis}_k(n) \subset \Sigma^*$, and $\operatorname{Int} \subset \Sigma^*$ denote the corresponding valid encoded strings. Polynomial-time linear algebra over $k$ means that, after extending malformed input strings to a fixed rejection output, the following string functions are polynomial-time computable: \begin{align*} \operatorname{rank}_{m,n}: \operatorname{Mat}_k(m,n) &\to \operatorname{Int}. \end{align*} \begin{align*} \operatorname{det}_n: \operatorname{Mat}_k(n,n) &\to \operatorname{Elt}_k. \end{align*} \begin{align*} \operatorname{kernel}_{m,n}: \operatorname{Mat}_k(m,n) &\to \operatorname{Basis}_k(n). \end{align*} \begin{align*} \operatorname{image}_{m,n}: \operatorname{Mat}_k(m,n) &\to \operatorname{Basis}_k(m). \end{align*} \begin{align*} \operatorname{solve}_{m,n}: \operatorname{Mat}_k(m,n) \times \operatorname{Vec}_k(m) &\to \operatorname{Vec}_k(n) \cup \{\bot\}. \end{align*} For valid encodings, $\operatorname{rank}_{m,n}$ outputs the rank in $\{0,\dots,\min\{m,n\}\}$, $\operatorname{det}_n$ outputs the encoded determinant, $\operatorname{kernel}_{m,n}$ outputs an encoded basis for $\ker(A) \subset k^n$, $\operatorname{image}_{m,n}$ outputs an encoded basis for $\operatorname{Range}(A) \subset k^m$, and $\operatorname{solve}_{m,n}(A,b)$ outputs either an encoded solution $x \in k^n$ of $Ax=b$ or $\bot$ when no solution exists. [/definition] This definition names a family of tasks rather than a single problem. The common feature is that row reduction changes the representation while preserving the solution space, but that observation alone is not enough for a complexity statement: the row operations must be performed uniformly, and the representation of field elements must stay under control. The algorithmic issue is whether these standard linear-algebra outputs can be produced with only polynomial overhead in the encoded matrix size. [quotetheorem:7898] This result is one reason linear algebra serves as a boundary between feasible and infeasible algebraic computation. The phrase “controlled field” is doing real work here: over finite fields with standard encodings, the entries never grow beyond a fixed-size representation, while over $\mathbb{Q}$ a bit-complexity proof usually invokes fraction-free elimination, modular reconstruction, or another method that prevents uncontrolled numerator and denominator growth. Once a problem can be reduced to solving linear equations over a field with this kind of representation control, it often enters polynomial time. [example: Syndrome Decoding with Fixed Error Radius] Let $C \subset \mathbb{F}_q^n$ be a linear code with parity-check matrix $H \in \mathbb{F}_q^{r \times n}$, so $c \in C$ exactly when $Hc=0$. Suppose the received word has the form $y=c+e$, where $c \in C$ and the error vector $e$ has Hamming weight at most a fixed constant $t$. Then the syndrome satisfies \begin{align*} Hy=H(c+e) \end{align*} by the definition of $y$, \begin{align*} H(c+e)=Hc+He \end{align*} by linearity of matrix multiplication, and therefore \begin{align*} Hy=0+He=He. \end{align*} For each subset $S\subseteq \{1,\dots,n\}$ with $|S|\le t$, let $H_S$ be the submatrix of $H$ formed from the columns indexed by $S$. An error vector supported on $S$ is determined by its coordinates $z\in \mathbb{F}_q^S$, and the equation $He=Hy$ becomes the linear system \begin{align*} H_S z=Hy. \end{align*} If this system has a solution $z$, define $e_S\in \mathbb{F}_q^n$ by putting $(e_S)_i=z_i$ for $i\in S$ and $(e_S)_i=0$ for $i\notin S$. Then $He_S=H_Sz=Hy$, so \begin{align*} H(y-e_S)=Hy-He_S=Hy-Hy=0. \end{align*} Thus $y-e_S\in C$, and $e_S$ is a compatible error vector. The number of supports that must be tried is \begin{align*} \sum_{j=0}^{t}\binom{n}{j}. \end{align*} For each $j\le t$ and $n\ge 1$, one has $\binom{n}{j}\le n^j\le n^t$, so \begin{align*} \sum_{j=0}^{t}\binom{n}{j}\le (t+1)n^t. \end{align*} Since $t$ is fixed, this is a polynomial in $n$. For each support, solving $H_Sz=Hy$ is a linear-algebra computation over the finite field $\mathbb{F}_q$, with at most $t$ unknowns and $r$ equations, so it takes polynomial time in the encoded input size. Hence bounded-radius syndrome decoding is polynomial time when the error radius $t$ is fixed. [/example] The phrase “fixed $t$” is essential. If $t$ is part of the input, the number of supports is no longer bounded by a fixed-degree polynomial in $n$, and the same strategy no longer gives a polynomial-time algorithm. ## Certificates, Verification, and Nondeterminism ### Verifiers and $NP$ Many algebraic problems have answers that are hard to find but easy to verify once supplied. A factorisation of an integer, a colouring of a graph, or a solution to a polynomial system can be checked by direct computation. This motivates a formal notion of efficient verification. [definition: Polynomial-Time Verifier] Let $L \subset \Sigma^*$ be a decision problem, and let $\Gamma$ be a finite alphabet. A polynomial-time verifier for $L$ is a polynomial-time decision algorithm \begin{align*} V: \Sigma^* \times \Gamma^* &\to \{0,1\} \end{align*} and a polynomial $p$ such that, for every $x \in \Sigma^*$, \begin{align*} x \in L \iff \text{there exists } c \in \Gamma^* \text{ with } |c| \le p(|x|) \text{ and } V(x,c)=1. \end{align*} The string $c$ is called a certificate. [/definition] The certificate must have polynomial length. Without that bound, a verifier could ask for a transcript of an exponentially long search, which would not explain feasible verification. The class $NP$ collects exactly the decision problems with such efficiently checkable yes-certificates. [definition: The Class $NP$] A decision problem $L \subset \Sigma^*$ belongs to $NP$ if it has a polynomial-time verifier. [/definition] The class $NP$ is not the class of problems that necessarily require exponential time. It is the class of problems whose yes-instances admit polynomial-size evidence that can be checked in polynomial time. Since a polynomial-time decision algorithm can verify membership without extra evidence, the next theorem places $P$ inside $NP$. [quotetheorem:6172] The certificate can be empty: if the decision problem is already solved in polynomial time, verification can ignore any witness and run the decision algorithm. [example: Integer Compositeness Has Short Certificates] Let \begin{align*} L=\{N\in \mathbb{N}: N \text{ is composite}\} \end{align*} where $N$ is encoded in binary. For an input $N$, a certificate is a binary integer $d$ such that $1<d<N$ and $d\mid N$. If $N$ is composite, then there exist integers $a,b$ with $1<a<N$, $1<b<N$, and \begin{align*} N=ab. \end{align*} Taking $d=a$ gives $1<d<N$, and $N=db$, so $d\mid N$. Conversely, if a certificate $d$ satisfies $1<d<N$ and $d\mid N$, then there is an integer $q$ such that \begin{align*} N=dq. \end{align*} Since $d<N$ and $N=dq$ with $d>0$, we have $q>1$. Thus $N$ is a product of two integers greater than $1$, so $N$ is composite. The verifier first compares the binary strings for $1$, $d$, and $N$ to check $1<d<N$. It then divides $N$ by $d$ and accepts exactly when the remainder is $0$. If the bit length of $N$ is $n$, then $N<2^n$. Since $d<N$, we also have $d<2^n$, so the bit length of $d$ is at most $n$. Binary comparison and schoolbook division of two integers with at most $n$ bits use a number of bit operations bounded by a fixed polynomial in $n$. Therefore compositeness has polynomial-size certificates that can be checked in polynomial time. [/example] This example also shows the difference between finding and checking. Trial division may take exponential time in the bit length, but a proposed divisor can be checked efficiently. ### Hardness and Completeness Efficient verification does not by itself give an efficient algorithm for finding a certificate. To compare the hardest verification problems with one another, we need a notion saying that every problem in $NP$ can be translated into a given problem with only polynomial overhead. [definition: $NP$-Hard Decision Problem] A decision problem $M \subset \Gamma^*$ is $NP$-hard if every problem $L \in NP$ satisfies $L \le_p M$. [/definition] Hardness alone does not require the target problem to have efficiently checkable certificates. A problem could be universal as a target for reductions while lying outside the verification framework that defines $NP$. The benchmark class used in reductions therefore imposes two requirements at once: the problem must itself have polynomial-size certificates that can be checked efficiently, and every problem with such certificates must reduce to it. [definition: $NP$-Complete Decision Problem] A decision problem $M \subset \Gamma^*$ is $NP$-complete if $M \in NP$ and $M$ is $NP$-hard. [/definition] For algebra, $NP$-completeness often appears when a compact algebraic object can encode arbitrary combinatorial choices. To use this method systematically, the theory needs at least one initial complete problem from which other hardness proofs can start. Boolean satisfiability provides that source problem: it converts the accepting computation of an arbitrary verifier into a finite logical formula of polynomial size. [quotetheorem:6199] Cook-Levin is the starting point for many hardness results. Once a problem is shown $NP$-complete, a polynomial-time algorithm for it would imply polynomial-time algorithms for every problem in $NP$. ## Pseudopolynomial Algorithms and Strong Polynomial Time ### Numerical Magnitudes Not every algorithm with a polynomial-looking bound is polynomial time. The distinction becomes sharp for numerical problems where the magnitude of the numbers and the number of bits needed to write them differ exponentially. Dynamic programming algorithms often expose this gap, so we first define the weaker pseudopolynomial notion. [definition: Pseudopolynomial-Time Algorithm] An algorithm for integer inputs is pseudopolynomial-time if its running time is bounded by a polynomial in the number of input integers and the magnitudes of those integers, rather than by a polynomial in the bit length of the input. [/definition] Pseudopolynomial time often reflects dynamic programming over possible numerical values. Such algorithms can be powerful in practice when the numbers are small, but they do not meet the bit-complexity standard for polynomial time. [example: Subset Sum Dynamic Programming] Given positive integers $a_1,\dots,a_n$ and a target $B$, the subset sum problem asks whether there is a set $I\subseteq \{1,\dots,n\}$ such that \begin{align*} \sum_{i\in I} a_i = B. \end{align*} Define a table entry $D(i,s)$ to mean that some subset of $\{1,\dots,i\}$ has sum $s$. The initial row is $D(0,0)=\text{true}$ and $D(0,s)=\text{false}$ for $1\le s\le B$. For $i\ge 1$, the subsets of $\{1,\dots,i\}$ either do not use $i$, giving the old condition $D(i-1,s)$, or do use $i$, in which case the remaining chosen elements must have sum $s-a_i$. Thus \begin{align*} D(i,s)=D(i-1,s)\ \text{or}\ \bigl(s\ge a_i \text{ and } D(i-1,s-a_i)\bigr). \end{align*} The answer is yes exactly when $D(n,B)$ is true. The row index $i$ has $n+1$ possible values, namely $0,1,\dots,n$, and the sum index $s$ has $B+1$ possible values, namely $0,1,\dots,B$. Hence the table has \begin{align*} (n+1)(B+1) \end{align*} entries. Each entry is computed from at most two earlier entries and one comparison $s\ge a_i$, so the number of table updates is bounded by a constant multiple of $(n+1)(B+1)$. Therefore the algorithm is polynomial in the numerical parameters $n$ and $B$. If $B$ is encoded in binary and has bit length $m$, then \begin{align*} m=\lfloor \log_2 B\rfloor+1. \end{align*} This implies $B<2^m$, and values with $B\ge 2^{m-1}$ have the same bit length $m$. For such inputs the table has at least \begin{align*} (n+1)(2^{m-1}+1) \end{align*} entries. Thus the same dynamic program can require exponentially many table entries in the bit length of $B$, so it is pseudopolynomial rather than polynomial-time in the standard binary input length. [/example] This example is important because it prevents a common misclassification. A dynamic program with a table indexed by numerical values is not automatically polynomial-time in the standard bit model. ### Strong Polynomial Time In optimisation and exact algebraic computation, another refinement is useful. We may want algorithms whose number of arithmetic operations is polynomial in the dimensions alone, independent of the bit lengths of coefficients, while bit growth is separately controlled. [definition: Strongly Polynomial-Time Algorithm] In the arithmetic-operation model for a numerical problem, an algorithm is strongly polynomial-time if the number of arithmetic operations is bounded by a polynomial in the number of input parameters, independent of the magnitudes of the numerical entries, and all intermediate numbers appearing in a bit implementation have bit length bounded by a polynomial in the input bit length. [/definition] This is the formulation used on this page; nearby optimisation literature sometimes packages the same idea with slightly different choices about the arithmetic model, encoding of rational numbers, or permitted intermediate quantities. In this arithmetic-operation setting, strong polynomial time is a refinement of ordinary bit-model polynomial time only when the bit-growth condition is included. It separates combinatorial structure from coefficient size and is especially significant in optimisation and exact linear programming. [remark: Linear Programming and Strong Polynomial Time] Linear programming has polynomial-time algorithms in the bit model, such as ellipsoid and interior-point methods. Whether there is a strongly polynomial-time algorithm for general linear programming is a major open problem. This connects polynomial time to the optimisation viewpoint developed in [Cambridge IB Optimisation](/page/Cambridge%20IB%20Optimisation). [/remark] ## Algebraic Applications and Boundaries Polynomial-time algorithms in algebra often arise from canonical forms. Row echelon form, Euclidean remainders, Smith normal form, Grobner bases in restricted settings, and normal forms for selected groups all try to replace search by a structured representative. To turn such examples into precise complexity statements, we need to define what it means for a property of algebraic objects to be decidable from an encoding. [definition: Polynomial-Time Decidable Algebraic Property] Let $\mathcal{C}$ be a class of finitely encoded algebraic objects, and let $\mathcal{P} \subset \mathcal{C}$ be a property. The property $\mathcal{P}$ is polynomial-time decidable with respect to an encoding $e: \mathcal{C} \to \Sigma^*$ if the language \begin{align*} L_{\mathcal{P}} = \{e(X) : X \in \mathcal{C} \text{ and } X \text{ has property } \mathcal{P}\} \end{align*} belongs to $P$. [/definition] This definition is the bridge from abstract algebra to complexity theory. It asks not only whether a property is mathematically meaningful, but whether it can be recognized uniformly from finite data. [example: Invertibility of a Matrix over a Finite Field] Let $A \in \mathbb{F}_q^{n \times n}$ be encoded by its $n^2$ entries. To decide whether $A$ is invertible, perform Gaussian elimination over $\mathbb{F}_q$ using the elementary row operations \begin{align*} R_i \leftrightarrow R_j, \end{align*} \begin{align*} R_i \leftarrow \lambda R_i \quad \text{with } \lambda \in \mathbb{F}_q^\times, \end{align*} \begin{align*} R_i \leftarrow R_i+\lambda R_j. \end{align*} Each operation is left multiplication by an invertible elementary matrix, so it preserves the rank of the matrix. The elimination algorithm searches each column for a nonzero pivot, swaps that pivot into the next unused row, scales if desired, and uses row additions to clear entries below the pivot. There are at most $n$ pivot stages. At one stage, finding a pivot checks at most $n$ entries, and clearing a column updates at most $n$ rows with at most $n$ field operations per row. Thus one stage uses at most a fixed constant times $n^2$ field operations, so all stages use at most a fixed constant times $n^3$ field operations. The resulting row echelon matrix $U$ has the same rank as $A$. If every column contains a pivot, then $U$ has $n$ pivot rows, so $\operatorname{rank}(A)=\operatorname{rank}(U)=n$, and the [linear map](/page/Linear%20Map) $x\mapsto Ax$ on $\mathbb{F}_q^n$ has trivial kernel. Hence $A$ is invertible. If some column has no pivot, then the echelon form has fewer than $n$ pivots, so $\operatorname{rank}(A)<n$, and the columns of $A$ are linearly dependent; therefore $A$ is not invertible. Under standard finite-field encodings, equality testing, zero testing, addition, subtraction, multiplication, and division by a nonzero element in $\mathbb{F}_q$ are polynomial-time computable in the encoding length of field elements. Since the matrix has $n^2$ encoded entries and Gaussian elimination uses only polynomially many such field operations, invertibility of an encoded matrix over $\mathbb{F}_q$ is polynomial-time decidable. [/example] This example contrasts with problems where the input describes an object indirectly. A finite group given by its full multiplication table has size $|G|^2$, so many operations polynomial in $|G|$ are polynomial in the input size. A group given by generators and relations can be exponentially more compact, and the same questions may become much harder. [example: Multiplication Table versus Generators] Let $G$ be a finite group. Suppose first that $G$ is encoded by its multiplication table, and that a subset $H\subset G$ is listed by its elements. To check whether $H$ is closed under multiplication, inspect every ordered pair $(h_1,h_2)\in H\times H$, look up the product $h_1h_2$ in the table, and test whether the resulting element appears in the list for $H$. The number of ordered pairs is \begin{align*} |H\times H|=|H||H|=|H|^2. \end{align*} Thus the multiplication part of the test uses exactly one table lookup for each ordered pair, hence at most $|H|^2$ table lookups. With a presentation by generators and relations, the input has a different form. For example, if \begin{align*} G=\langle s_1,\dots,s_m \mid R\rangle, \end{align*} then an element is represented by a word in the symbols $s_1,\dots,s_m$ and their formal inverses. To test closure of a listed set of words $H=\{w_1,\dots,w_\ell\}$, one would need to decide, for each product word $w_iw_j$, whether it represents the same group element as one of the listed words $w_1,\dots,w_\ell$. That comparison is the word problem for the presentation: decide whether two words represent the same element, equivalently whether $uv^{-1}$ represents the identity. Thus the multiplication-table encoding makes multiplication a table lookup, while the generator-and-relation encoding makes even equality of represented elements part of the computation. The encoding changes the algorithmic problem, not just the notation. [/example] The lesson is methodological: algebraic complexity statements should always say how the input is represented. The same mathematical noun can define different languages under different encodings. [remark: Encoding Sensitivity] A claim that an algebraic problem is polynomial-time decidable is incomplete unless it specifies a finite encoding of the input objects and a cost model for the permitted elementary operations. [/remark] The remark is a discipline for making complexity statements mathematically testable. It is especially important when moving between concrete finite structures and compact presentations. ## Beyond and Connected Topics Polynomial-time algorithms are the entry point to computational complexity. The next layer is the comparison between $P$, $NP$, and $NP$-complete problems, where reductions become the main method for proving that a problem is at least as hard as a benchmark problem. In optimisation, polynomial time separates algorithms with scalable worst-case guarantees from methods that may work well only on selected instances. Linear programming, integer programming, network flows, and dynamic programming all refine the basic notion in different directions; [Cambridge IB Optimisation](/page/Cambridge%20IB%20Optimisation) is a natural continuation. Coding theory uses polynomial-time algorithms both constructively and adversarially. Encoding and syndrome computation for linear codes are efficient linear algebra tasks, while general decoding problems can be hard when the error radius is part of the input. This connects directly with [Cambridge II Coding and Cryptography](/page/Cambridge%20II%20Coding%20and%20Cryptography). Graph theory supplies many standard reductions and benchmark problems. Colouring, matching, flows, cuts, and connectivity illustrate how small changes in the problem statement can move a task into or out of known polynomial-time territory; see [Cambridge II Graph Theory](/page/Cambridge%20II%20Graph%20Theory). Number theory gives some of the most important examples of bit-complexity thinking. Euclidean algorithms, modular arithmetic, primality testing, factorisation, and arithmetic in number fields all depend on measuring the length of integer encodings rather than the magnitudes of the integers themselves. For the algebraic background, see [Cambridge II Number Fields](/page/Cambridge%20II%20Number%20Fields). A further direction is algebraic complexity theory, which studies arithmetic circuits, polynomial identity testing, matrix multiplication, and the complexity of computing polynomial families. Here the input may be a polynomial, a circuit, or an oracle for evaluation, so the encoding question remains central. ## References Androma, [Cambridge IB Optimisation](/page/Cambridge%20IB%20Optimisation). Androma, [Cambridge II Coding and Cryptography](/page/Cambridge%20II%20Coding%20and%20Cryptography). Androma, [Cambridge II Graph Theory](/page/Cambridge%20II%20Graph%20Theory). Androma, [Cambridge II Number Fields](/page/Cambridge%20II%20Number%20Fields). Christos H. Papadimitriou, *Computational Complexity* (1994). Michael Sipser, *Introduction to the Theory of Computation* (1997). Sanjeev Arora and Boaz Barak, *Computational Complexity: A Modern Approach* (2009). Joachim von zur Gathen and Jurgen Gerhard, *Modern Computer Algebra* (1999).