Demystifying Computational Complexity: P, NP, Cook's Theorem, and the Foundations of Computer Science

Verified Sources

May 26, 2026

In the study of computer science, understanding the limits of computation is as vital as designing efficient algorithms. Computational complexity theory provides a rigorous mathematical framework to classify problems based on the resources—specifically time and memory—required to solve them .

At the heart of this field lies the distinction between a Decision problem, which requires a simple binary output, and search or optimization problems. To formalize these concepts, computer scientists rely on a theoretical model known as a Deterministic Turing Machine. By analyzing how the execution time of these machines scales with input size, we can group problems into a specific Complexity class .

NP-completeness - Wikipedia - Overview of computational complexity classes and the P vs NP problem. ↩ ↩²

NP-Hard and NP-Complete Problems Explained

Classifying Complexity: P, NP, NP-Complete, and NP-Hard

To understand computational boundaries, we define four core complexity classes based on how efficiently we can solve or verify them.

1. The Class $\mathsf{P}$

The class $\mathsf{P}$ consists of all decision problems that can be solved by a deterministic Turing machine in Polynomial time . Formally: $\mathsf{P} = \bigcup_{k \ge 1} \text{TIME}(n^k)$ Problems in $\mathsf{P}$ are considered "tractable" or efficiently solvable. Examples include finding the shortest path in a graph or determining if a number is prime.

2. The Class $\mathsf{NP}$

The class $\mathsf{NP}$ (Nondeterministic Polynomial time) consists of decision problems that can be solved in polynomial time by a Nondeterministic Turing Machine . Alternatively, it is the class of problems for which a proposed "yes" instance can be verified in polynomial time by a deterministic machine when provided with a certificate (or witness) .

3. The Class $\mathsf{NP\text{-}complete}$

A problem $L$ is $\mathsf{NP\text{-}complete}$ if it satisfies two conditions:

$L \in \mathsf{NP}$
Every problem in $\mathsf{NP}$ can be reduced to $L$ in polynomial time via a Karp reduction .

These are the "hardest" problems in $\mathsf{NP}$ . If any single $\mathsf{NP\text{-}complete}$ problem can be solved in polynomial time, then $\mathsf{P} = \mathsf{NP}$ .

4. The Class $\mathsf{NP\text{-}hard}$

A problem $H$ is $\mathsf{NP\text{-}hard}$ if every problem in $\mathsf{NP}$ can be reduced to $H$ in polynomial time. Unlike $\mathsf{NP\text{-}complete}$ problems, $\mathsf{NP\text{-}hard}$ problems do not have to be in $\mathsf{NP}$ . They may not even be decision problems or even decidable (e.g., the Halting Problem) .

Complexity Class	Verification Time	Solving Time (Deterministic)	Examples
$\mathsf{P}$	Polynomial	Polynomial	Sorting, Shortest Path, Primality Testing
$\mathsf{NP}$	Polynomial	Exponential (best known)	Traveling Salesperson, Sudoku, Integer Partitioning
$\mathsf{NP\text{-}complete}$	Polynomial	Exponential (best known)	3-SAT, Clique, Vertex Cover
$\mathsf{NP\text{-}hard}$	Not necessarily polynomial	Exponential (or undecidable)	Halting Problem, TSP (optimization version)

NP-completeness - Wikipedia - Overview of computational complexity classes and the P vs NP problem. ↩ ↩² ↩³ ↩⁴
Cook–Levin theorem - GeeksforGeeks - Detail on Cook's Theorem and Karp's 21 reductions. ↩

A deterministic machine verifies a solution in polynomial time. For example, given a proposed factor $p$ of $N$ , we can verify if $p$ divides $N$ using a single division step:

1def verify(N, p):
2    return N % p == 0

Growth Rate Comparison of Complexity Classes

Number of operations required for different complexity functions at N = 15

The Millennium Prize Problem

The question of whether $\mathsf{P} = \mathsf{NP}$ is one of the seven Millennium Prize Problems established by the Clay Mathematics Institute . A correct proof or disproof carries a $1,000,000 reward.

NP-completeness - Wikipedia - Overview of computational complexity classes and the P vs NP problem. ↩

Cook's Theorem (The Cook-Levin Theorem)

Before 1971, computer scientists knew that many computational problems were highly difficult, but they lacked a formal way to prove that these problems shared a common ceiling of complexity. Stephen Cook (and independently Leonid Levin) solved this by formulating what is now known as Cook's Theorem (or the Cook-Levin Theorem) .

Formal Statement

Theorem: The Boolean Satisfiability problem (SAT) is $\mathsf{NP\text{-}complete}$ .

To prove that SAT is $\mathsf{NP\text{-}complete}$ , Cook had to demonstrate two things:

$\text{SAT} \in \mathsf{NP}$ (which is simple, as a given truth assignment can be evaluated in polynomial time).
For every possible language $A \in \mathsf{NP}$ , there exists a polynomial-time reduction $A \le_{\text{P}} \text{SAT}$ .

The genius of Cook's proof was that instead of reducing individual problems one by one, he reduced the definition of nondeterministic polynomial-time computation itself to a Boolean formula . He represented the history of any Nondeterministic Turing Machine (NTM) run on an input $w$ as a grid of configurations, called a Tableau .

Cook–Levin theorem - GeeksforGeeks - Detail on Cook's Theorem and Karp's 21 reductions. ↩ ↩²
The Cook-Levin Theorem - Cornell University - Mid-level overview and mathematical proof variables of the Cook-Levin Theorem. ↩ ↩²

The Cook-Levin Reduction Process

1
Step 1
Given a Nondeterministic Turing Machine $M$ and an input $w$ , we construct a $(n^k) \times (n^k)$ grid (tableau) . Each row represents the configuration of the machine (tape contents, state, head position) at a specific time step $t$ up to the polynomial time bound $n^k$ .

Footnotes

The Cook-Levin Theorem - Cornell University - Mid-level overview and mathematical proof variables of the Cook-Levin Theorem. ↩
2
Step 2
We define boolean variables to represent the state of the tableau: \

$x_{i, j, s} = 1$ if cell $(i,j)$ contains symbol $s$ . \

$y_{i, t} = 1$ if the tape head is at cell $i$ at time $t$ . \

$z_{q, t} = 1$ if the machine is in state $q$ at time $t$ .
3
Step 3
We construct the final Boolean formula $\phi = \phi_{\text{cell}} \land \phi_{\text{start}} \land \phi_{\text{move}} \land \phi_{\text{accept}}$ : \

$\phi_{\text{cell}}$ ensures each cell contains exactly one symbol. \

$\phi_{\text{start}}$ ensures the first row represents the initial configuration with input $w$ . \

$\phi_{\text{move}}$ ensures transition rules of the Turing Machine are strictly followed between row $t$ and $t+1$ . \

$\phi_{\text{accept}}$ ensures the machine reaches an accepting state by the final step.
4
Step 4
The number of cells in the tableau is $(n^k)^2 = n^{2k}$ . Since the number of variables and constraints per cell is constant (dependent only on the fixed machine $M$ , not the input $w$ ), the total size of the Boolean formula $\phi$ is $O(n^{2k})$ , which is polynomial in the input size $n$ .

Footnotes

The Cook-Levin Theorem - Cornell University - Mid-level overview and mathematical proof variables of the Cook-Levin Theorem. ↩

NP-Hard vs. NP-Complete

Remember that NP-hard problems do not have to be in $\mathsf{NP}$ . For example, the Halting Problem is NP-hard because any $\mathsf{NP}$ problem can be reduced to it, but it is undecidable, meaning it is not in $\mathsf{NP}$ .

NP-completeness - Wikipedia - Overview of computational complexity classes and the P vs NP problem. ↩

Historical Milestones of Complexity Theory

Cook's Seminal Paper

1971

Stephen Cook publishes 'The Complexity of Theorem Proving Procedures', proving that SAT is NP-complete ."

Cook–Levin theorem - GeeksforGeeks - Detail on Cook's Theorem and Karp's 21 reductions. ↩

Karp's 21 Problems

1972

Richard Karp publishes his landmark paper showing that 21 diverse combinatorial problems are also NP-complete, establishing the universality of the class ."

Cook–Levin theorem - GeeksforGeeks - Detail on Cook's Theorem and Karp's 21 reductions. ↩

Levin's Independent Discovery

1973

Leonid Levin independently formulates 'universal search problems' in the Soviet Union, leading to the co-naming of the Cook-Levin Theorem."

Modern Complexity Landscape

Present

Thousands of problems across computer science, biology, economics, and physics are proven to be NP-complete, remaining computationally challenging."

Why Cook's Theorem is a Foundational Result

Cook's Theorem is widely considered one of the most important results in computational complexity theory for several key reasons:

It Established the Existence of $\mathsf{NP\text{-}complete}$ Problems: Before this theorem, it was unknown whether a "hardest" problem in $\mathsf{NP}$ actually existed. Cook proved that SAT acts as a universal representative for the entire class $\mathsf{NP}$ .
It Sparked the "Complexity Explosion" via Reductions: Once SAT was proven to be $\mathsf{NP\text{-}complete}$ , computer scientists no longer had to map Turing machine computations to prove other problems hard. Instead, they could simply reduce SAT to their target problem. Richard Karp used this technique to show that 21 classic problems (such as the Clique problem and Vertex Cover) were also $\mathsf{NP\text{-}complete}$ .
It Unified Practical and Theoretical Computer Science: Cook's Theorem linked diverse, seemingly unrelated problems across scheduling, logic, graph theory, and cryptography under a single mathematical umbrella. It explained why decades of algorithmic efforts had failed to find efficient solutions for these problems.

Cook–Levin theorem - GeeksforGeeks - Detail on Cook's Theorem and Karp's 21 reductions. ↩

Frequently Asked Questions & Edge Cases

Knowledge Check

Question 1 of 3

Q1Single choice

What does the 'NP' in complexity class NP stand for?

Non-Polynomial

Nondeterministic Polynomial time

Normal Polynomial

Network Protocol

Explore Related Topics

Complexity Analysis of a Divide-and-Conquer Recurrence

The course explains how to determine the asymptotic complexity of the divide‑and‑conquer recurrence  $T(n)=2T(n/4)+n^{2}\log n$ .

Identify parameters: $a=2$ , $b=4$ , $f(n)=n^{2}\log n$ .
Critical exponent $\log_b a=\log_4 2=0.5$ , so leaf cost grows as $n^{0.5}$ .
Since $f(n)=\Omega\!\big(n^{0.5+\epsilon}\big)$ for $\epsilon\le1.5$ , Case 3 of the Master Theorem applies.
Regularity condition holds with $c=1/8<1$ , confirming dominance of the root work.
Consequently $T(n)=\Theta(n^{2}\log n)$ , which is also derived via recursion‑tree and Akra‑Bazzi methods.

Dynamic Programming and Greedy Algorithms: Comparative Analysis, Failure Cases, and Core DP Properties

The article contrasts greedy algorithms with dynamic programming, shows when greedy fails and DP is necessary, and explains DP’s core properties of optimal substructure and overlapping subproblems.

Greedy makes irrevocable local choices and works only with the $greedy\text{-}choice$ property, while DP stores and reuses subproblem results to guarantee optimality.
Counterexamples such as coin change ( $\{1,3,4\}$ for amount 6) and $0/1$ knapsack illustrate failures of greedy and the need for DP recurrences like $dp[x]=1+\min_{c\le x}dp[x-c]$ and $dp[i][w]=\max(dp[i-1][w],\,v_i+dp[i-1][w-w_i])$ .
DP relies on $optimal\ substructure$ to form recurrences and on overlapping subproblems to justify caching.
Design steps: recognize structure, detect repetition, formulate recurrence, compute once (memoization/tabulation), optionally reconstruct solution.
Rule of thumb: use greedy if local choices can be proved globally safe; otherwise apply DP.

Minimum Spanning Trees: Concept, Prim’s vs Kruskal’s, and Complexity Analysis

Browse all research articles

Demystifying Computational Complexity: P, NP, Cook's Theorem, and the Foundations of Computer Science

Footnotes

NP-Hard and NP-Complete Problems Explained

Classifying Complexity: P, NP, NP-Complete, and NP-Hard

1. The Class P\mathsf{P}P

2. The Class NP\mathsf{NP}NP

3. The Class NP-complete\mathsf{NP\text{-}complete}NP-complete

4. The Class NP-hard\mathsf{NP\text{-}hard}NP-hard

Footnotes

Growth Rate Comparison of Complexity Classes

The Millennium Prize Problem

Footnotes

Cook's Theorem (The Cook-Levin Theorem)

Formal Statement

Footnotes

The Cook-Levin Reduction Process

Footnotes

Footnotes

NP-Hard vs. NP-Complete

Footnotes

Historical Milestones of Complexity Theory

Cook's Seminal Paper

Footnotes

Karp's 21 Problems

Footnotes

Levin's Independent Discovery

Modern Complexity Landscape

Why Cook's Theorem is a Foundational Result

Footnotes

Frequently Asked Questions & Edge Cases

Knowledge Check

Explore Related Topics

1. The Class $\mathsf{P}$

2. The Class $\mathsf{NP}$

3. The Class $\mathsf{NP\text{-}complete}$

4. The Class $\mathsf{NP\text{-}hard}$