What Defines Complexity Class P in Classical Computing?

Complexity class P is the set of all decision problems that can be solved by a deterministic Turing machine in polynomial time relative to the size of the input. In classical computing and computational complexity theory, P serves as the standard mathematical formalization of problems that are considered efficiently solvable or tractable.

Formal Definition of Class P

A decision problem is a computational problem with a yes-or-no answer, formally represented as a formal language \(L \subseteq \{0, 1\}^*\) over a binary alphabet. A deterministic Turing machine \(M\) decides a language \(L\) in time \(T(n)\) if, for every input string \(x\) of length \(n = |x|\), \(M\) halts after at most \(T(n)\) steps and outputs whether \(x \in L\).

Using deterministic time complexity classes \(\text{DTIME}(T(n))\), the class \(\mathbf{P}\) is defined as the union over all polynomial time bounds:

\[\mathbf{P} = \bigcup_{k \ge 1} \text{DTIME}(n^k)\]

This means a problem belongs to \(\mathbf{P}\) if there exists a deterministic algorithm and a constant \(k \ge 1\) such that the algorithm solves every instance of size \(n\) in \(O(n^k)\) steps.

Key Characteristics

  • Deterministic execution: Every step of the computation is uniquely determined by the current state and the symbol being read, with no branching or guessing.
  • Polynomial time bound: The worst-case running time grows no faster than a polynomial function of the input length \(n\), such as \(O(n)\), \(O(n \log n)\), or \(O(n^3)\), rather than exponentially like \(O(2^n)\).
  • Machine independence: By the Church-Turing thesis and its extended polynomial-time variant, any reasonable deterministic classical model of computation (such as a multi-tape Turing machine or a random-access machine) can simulate another with at most a polynomial slowdown. Consequently, \(\mathbf{P}\) is invariant across standard classical computing models.
  • Closure properties: The class \(\mathbf{P}\) is closed under complement, union, intersection, and polynomial-time reductions.

Examples of Problems in P

Many foundational problems in computer science belong to \(\mathbf{P}\):

  • Shortest path: Finding the shortest path between two vertices in a weighted graph with non-negative weights using Dijkstra's algorithm.
  • Linear programming: Solving systems of linear inequalities to optimize a linear objective function.
  • Primality testing: Determining whether an integer \(N\) is prime, proven to be in \(\mathbf{P}\) by the AKS primality test in \(O((\log N)^k)\) time, where \(\log N\) is the bit-length of the input.
  • Sorting and searching: Sorting a list of \(n\) elements in \(O(n \log n)\) time or finding a greatest common divisor using the Euclidean algorithm.

Role in Complexity Theory

Class \(\mathbf{P}\) sits at the foundation of the complexity hierarchy. It is a subset of \(\mathbf{NP}\) (nondeterministic polynomial time), because any deterministic polynomial-time machine is a special case of a nondeterministic one. Whether \(\mathbf{P} = \mathbf{NP}\) remains the most famous open problem in computer science. Additionally, \(\mathbf{P}\) is contained within \(\mathbf{PSPACE}\) (problems solvable using polynomial space) and \(\mathbf{EXP}\) (problems solvable in exponential time).