The Class P

A decision problem asks a yes/no question about an input, and is formalized as a language: the set of all strings (encoded inputs) for which the answer is "yes." A Turing machine $M$ decides a language $L$ if, on every input, $M$ halts and accepts exactly when the input is in $L$, and rejects otherwise. This total, always-halting behavior is what separates deciding a language from merely recognizing it. The time complexity of $M$ is a function $t(n)$ giving the maximum number of steps $M$ takes on any input of length $n$ (worst case). We say $M$ runs in polynomial time if there is a constant $k$ such that $t(n) = O(n^k)$. The class $\mathbf{P}$ is then defined as

Two design choices inside this definition deserve attention. First, we measure time as a function of $n$, the length of the encoded input string, not of some "natural size" like the numeric value of an integer — this is why primality testing on an integer $N$ is polynomial only if it runs in time polynomial in $\log N$, the number of bits needed to write $N$ down, not in $N$ itself. Second, the polynomial bound is a worst-case guarantee: it must hold for every input of a given length, not merely on average or for friendly instances. The reason P deserves to be called the class of tractable problems, rather than an arbitrary bookkeeping definition, is a robustness theorem: switching between reasonable deterministic computational models changes the running time by at most a polynomial factor. A single-tape Turing machine can simulate a multi-tape Turing machine with only a quadratic slowdown; a multi-tape machine can simulate a random-access machine (the abstraction behind real computers) with only polynomial overhead; different encodings of the same mathematical object (adjacency lists vs. adjacency matrices for a graph, say) change input length by at most a polynomial factor. Since polynomials composed with polynomials are still polynomials, none of these choices moves a problem into or out of P. This closure property is exactly what licenses the informal habit of describing algorithms in pseudocode or high-level programming languages, rather than raw Turing-machine transitions, when arguing that a problem is "in P."

To show a language $L$ is in P, you exhibit any deterministic algorithm that decides $L$ and runs in polynomial time — you do not need to build a literal Turing machine, thanks to the robustness argument above. The general recipe has three parts: 1. Specify the encoding. Fix how inputs (graphs, numbers, formulas) are represented as strings, and let $n$ denote the length of that encoding. 2. Describe the algorithm. Give a step-by-step procedure that always halts and outputs accept/reject correctly. 3. Bound the running time. Show the number of elementary steps is $O(n^k)$ for some fixed $k$, independent of the specific input (only depending on $n$). The canonical textbook example is PATH:

Here $\langle G, s, t\rangle$ denotes a reasonable encoding of the graph $G$ together with distinguished nodes $s$ and $t$ — for instance, an adjacency list. The algorithm that decides PATH is breadth-first search (BFS), marking every node reachable from $s$ and then checking whether $t$ got marked. ``` Algorithm DECIDE-PATH(G, s, t): // G is given as an adjacency list over vertex set V, edge set E // n = |V| + |E| (roughly the encoding length) if s == t: return ACCEPT create boolean array visited[1..|V|], all initialized to false create empty queue Q visited[s] = true enqueue(Q, s) while Q is not empty: u = dequeue(Q) for each edge (u, v) in adjacency-list(u): if not visited[v]: visited[v] = true if v == t: return ACCEPT enqueue(Q, v) return REJECT ``` The algorithm never guesses, never backtracks, and never revisits a node twice — every vertex is enqueued at most once, guaranteeing termination. Correctness rests on a simple loop invariant, proved by induction on the number of iterations of the while-loop: > Invariant. At every point in the algorithm, `visited[v] = true` if and only if there is a directed path from $s$ to $v$ using only vertices that have already been dequeued as intermediate stops, or $v = s$. Formally, one shows by induction on BFS "layers" (distance from $s$) that a vertex $v$ is marked visited exactly when the shortest directed path from $s$ to $v$ has been discovered — every vertex reachable from $s$ eventually gets enqueued, because if $u$ is reachable and visited, every out-neighbor of $u$ becomes visited in the same iteration that $u$ is dequeued. Since the graph is finite, this process reaches a fixed point where no more nodes can be marked, and at that fixed point the visited set is exactly the set of vertices reachable from $s$. So the algorithm accepts iff $t$ is reachable from $s$, iff $\langle G,s,t\rangle \in$ PATH. The following diagram shows a small instance being processed by BFS layer by layer, alongside the queue state, making the invariant concrete.

The trace box at the bottom of the figure mirrors exactly what the pseudocode's queue does: $s$ is dequeued first and pushes $a, b$; then $a$ is dequeued and pushes $c$; then $b$ is dequeued (its only neighbor $c$ is already visited, so nothing new is added); then $c$ is dequeued and discovers $t$, causing immediate acceptance. Node $d$ is never visited because it is unreachable from $s$ along the directed edges shown — the algorithm correctly never marks it.

Time complexity of DECIDE-PATH. Let $n$ be the length of the encoding of $\langle G, s, t\rangle$, so $n = \Theta(|V| + |E|)$ under a standard adjacency-list encoding (every vertex and every edge contributes a constant number of symbols). The algorithm:

• Initializes `visited` in $O(|V|)$ time.
• Enqueues and dequeues each vertex at most once, because the `visited` check prevents duplicate enqueues — this gives $O(|V|)$ queue operations, each $O(1)$.
• For each dequeued vertex $u$, scans its adjacency list, whose total length summed over all $u$ is exactly $|E|$ (each directed edge appears once). So the total work done across all scans is $O(|E|)$.

Adding these up gives total running time $O(|V| + |E|) = O(n)$ — in fact linear in the input size, comfortably a polynomial (take $k=1$). This places PATH in P.

Why "polynomial in the model" is not fragile. One might worry: what if we had used a single-tape Turing machine instead of pseudocode with arrays and queues? The standard simulation theorems answer this. A $k$-tape Turing machine running in time $t(n)$ can be simulated by a single-tape machine in time $O(t(n)^2)$; a random-access machine (arrays with $O(1)$-time indexed access, as used in the pseudocode above) can be simulated by a multi-tape Turing machine with only polynomial overhead (typically $O(t(n)^2)$ or better, depending on the RAM's word-size assumptions). Composing a polynomial with a polynomial is still a polynomial:

So if an algorithm described in RAM pseudocode runs in polynomial time, the Turing machine realizing that algorithm also runs in polynomial time, just with a possibly larger exponent. This is precisely why complexity theorists are permitted to design algorithms in high-level pseudocode (as above) and immediately conclude Turing-machine membership in P, without ever writing transition tables.

Correctness recap. The BFS invariant stated earlier — visited$(v)$ holds iff $v$ is reachable from $s$ through already-processed vertices — is proved by strong induction on the order in which vertices are dequeued, using the fact that BFS processes vertices in non-decreasing order of distance from $s$ (a consequence of the FIFO queue discipline: a vertex at distance $d$ is only enqueued after all vertices at distance $< d$ have been dequeued). Termination is guaranteed because the queue can hold each of the $|V|$ vertices at most once, so the loop runs at most $|V|$ iterations of dequeuing, each doing bounded work. Total correctness (halts + always gives right answer) is what makes DECIDE-PATH a decider, not just a recognizer — crucial for language membership in P, since P is defined via total, always-halting machines.

Honesty about tradeoffs. Polynomial time is a coarse, asymptotic, worst-case notion. An algorithm running in $O(n^{100})$ is "efficient" by this definition yet catastrophic in practice; an algorithm running in $O(2^{0.0001 n})$ is "inefficient" by this definition yet perfectly fine for small $n$. P is the right theoretical dividing line for classifying problems by inherent difficulty, but engineers still care about the hidden constants, the actual exponent, and average-case behavior — none of which the definition of P sees.

Let's trace DECIDE-PATH on a concrete instance step by step, using the exact graph from the figure: vertices $\{s, a, b, c, d, t\}$, directed edges $s\to a$, $s \to b$, $a \to c$, $b \to c$, $c \to t$, and $d$ isolated (no incoming or outgoing edges relevant to reachability from $s$). We ask: is $\langle G, s, t\rangle \in$ PATH?

The algorithm halts and accepts after 5 constant-time iterations of the outer loop on a graph with $|V|=6$ and $|E|=5$, well within the $O(|V|+|E|) = O(11)$ bound. Vertex $d$ was never touched — correctly, since it is not reachable from $s$. If we instead asked whether $\langle G, s, d\rangle \in$ PATH, the same algorithm would exhaust the queue (after step 4, the queue empties without ever marking $d$) and correctly REJECT. To see the polynomial bound is not just a coincidence on this tiny example, imagine scaling up: chain together $m$ copies of this pattern in sequence ($s \to a_1 \to b_1 \to \cdots \to a_m \to b_m \to t$), producing a graph with $n = \Theta(m)$ vertices and edges. BFS still visits each vertex once and scans each edge once, giving running time $\Theta(m) = \Theta(n)$ — linear, hence polynomial, regardless of how large $m$ grows. This is the essence of "efficiently solvable independent of instance size": the growth rate of the work, not the work on one fixed instance, is what membership in P certifies.

Every time a GPS app finds any route between two points before optimizing for the shortest one, it is implicitly relying on the fact that reachability — PATH — is decidable in linear time; the same BFS/DFS machinery underlies network routing protocols, dependency resolution in build systems and package managers, and garbage collectors tracing reachable objects in memory. Compilers rely on P-time algorithms for parsing (context-free language recognition via dynamic programming), register allocation heuristics, and data-flow analysis. Databases lean on polynomial-time query evaluation and indexing structures. Cryptographic protocols are built on the presumed hardness of certain problems believed to lie outside P (like integer factorization), making the boundary of P itself a load-bearing wall for internet security. The entire research program of proving polynomial-time algorithms — or proving hardness via Polynomial-Time Reductions to problems believed to be outside P — traces back to the clean, robust definition given here, and the still-unresolved question of whether P equals The Class NP is widely regarded as the most important open problem in theoretical computer science.

Ask the tutor: How does the definition of P change (if at all) when we allow randomized or nondeterministic machines instead of deterministic ones?