Computational Complexity

Introduction

Computers can perform billions of operations, but speed alone does not make every computational problem easy. Computational complexity studies how the resources needed to solve a problem grow as the input becomes larger. Typical resources are time, memory, randomness, communication, or the number of processors. At Grades 11–13, the central goal is to learn how to compare algorithms by growth rates and how to reason about problems for which no efficient algorithm is known.

This topic links algorithms, asymptotic notation, models of computation, graph theory, Boolean satisfiability, and the famous P versus NP question. You will work with proofs, examples, experiments, and small programs rather than merely memorize labels.

The diagram above shows relationships among several important complexity classes. Such diagrams summarize known containments, but they should not be read as proving that every boundary is strict. Some major separations remain open research questions.

The MIT OpenCourseWare lecture above gives a university-level bridge from algorithm analysis to P, NP, completeness, and reductions. Use it selectively: pause after each new term and restate the idea in your own words.

Learning Goals

By the end of this aiMOOC, you should be able to explain why input size matters, estimate common time-complexity growth rates, distinguish decision and optimization problems, describe the classes P and NP, explain NP-hardness and NP-completeness, trace the logic of a polynomial-time reduction, and discuss why complexity theory matters for real computing.

You should also be able to separate three different questions: Can a problem be computed at all? Can it be computed with limited resources? Can it be solved efficiently enough for the input sizes we care about? These questions belong to related but distinct areas of theoretical computer science.

Measuring Computational Resources

Input Size and Scaling

Complexity analysis begins with an input-size measure, usually written as n. For a list, n may be the number of elements. For a graph, the input description may depend on the numbers of vertices and edges. For an integer, the input size is normally the number of bits needed to encode it, not the numerical value of the integer itself.

This distinction is essential. An algorithm that takes a number of steps proportional to the value of an integer N can be exponential in the bit-length of N, because writing N in binary requires only about log2 N bits.

Complexity theory usually asks how resource use grows as input size grows. Exact running times depend on hardware, programming language, compiler, and implementation, but growth rates allow broader comparisons.

Big O and Common Growth Rates

Big O notation is commonly used to express an asymptotic upper bound. If an algorithm takes O(n²) time, the statement says that beyond some sufficiently large input size, its running time is bounded above by a constant multiple of n². Big O does not by itself give the exact running time, and it can be a loose upper bound.

Common growth rates include constant O(1), logarithmic O(log n), linear O(n), linearithmic O(n log n), polynomial O(n^k) for a fixed constant k, and exponential forms such as O(2^n). Factorial growth O(n!) is even faster than ordinary exponential growth.

For small inputs, a theoretically slower algorithm can sometimes win because constants and implementation details matter. For large inputs, however, the growth rate often dominates.

This Computerphile video uses sorting to connect experimental running time with Big O notation. While watching, identify which observations are empirical measurements and which claims are asymptotic statements.

Time Complexity and Space Complexity

Time complexity counts computational steps as a function of input size. Space complexity measures the amount of memory used. These resources can trade off against one another: an algorithm may use extra memory to avoid recomputing values, while another may save memory at the cost of additional time.

Complexity analysis can study best-case, average-case, or worst-case behavior. Theoretical complexity classes are often defined using worst-case resource bounds because worst-case guarantees are precise and composable. In applications, average-case and distribution-specific behavior may also be important.

Models of Computation

Why Use an Abstract Machine?

To define classes such as P and NP rigorously, computer scientists need a mathematical model of computation. A Turing machine is a simple abstract model consisting of a control mechanism, a read-write head, and a tape divided into cells. It is not intended as a blueprint for a modern computer; it is a mathematical reference model for what an algorithm can do.

Different reasonable general models of computation can differ in exact step counts, yet they are robust enough that polynomial-time distinctions are not normally destroyed by switching between standard models. This robustness is one reason polynomial time became central in complexity theory.

The video above introduces Turing machines in accessible language. As you watch, focus on the idea that a very simple machine can formalize the execution of an algorithm.

Computability Is Not the Same as Complexity

Computability theory asks whether an algorithm exists at all for a problem. Complexity theory asks how many resources are required, usually for problems that are computable. An undecidable problem is not merely a problem with a very large running time; it has no algorithm that correctly solves every instance and always halts.

The distinction matters when discussing difficult problems. Saying that a problem is NP-complete does not mean it is undecidable. NP-complete decision problems are decidable; the issue is that no polynomial-time algorithm is currently known for them.

Decision Problems, Search, and Optimization

A decision problem has a yes-or-no answer. Complexity classes such as P and NP are usually defined for decision problems because this makes reductions and class membership precise.

A related search problem asks you to find a solution, and an optimization problem asks you to find the best solution according to an objective. These versions can be closely related but are not literally the same problem.

For example, the travelling salesperson decision problem can ask whether there is a tour of total length at most a given bound. The optimization version asks for the shortest possible tour. The decision version is NP-complete, while the standard optimization version is NP-hard.

The two images show the contrast between an instance that needs a tour and a particular solved tour. For small instances you can inspect possibilities directly; as the number of locations grows, the number of possible tours grows explosively.

The Complexity Class P

P is the class of decision problems that can be solved by a deterministic algorithm in polynomial time. Informally, if the running time is bounded by n^k times a constant for some fixed k, the problem belongs to P.

Examples include many standard tasks such as checking whether a graph is connected, finding a shortest path in a graph with nonnegative edge weights, and testing whether a list contains a target value. The exact algorithm and representation matter, but the defining idea is a deterministic polynomial-time bound.

Polynomial time is often used as a mathematical model of tractability. It is not a guarantee of practical speed. An algorithm with running time n^100 is polynomial but useless for most input sizes, while a carefully designed exponential algorithm can be practical when n is very small.

The Complexity Class NP

NP stands for nondeterministic polynomial time. One equivalent and especially useful definition is: NP contains the decision problems for which every yes-instance has a polynomial-size certificate that can be verified in polynomial time by a deterministic algorithm.

Suppose someone gives you a proposed Hamiltonian cycle in a graph. You can efficiently check whether the listed vertices form a cycle, whether every required vertex appears exactly once, and whether all listed edges exist. Finding such a cycle may be difficult, but checking a proposed one is straightforward.

A crucial fact is P is contained in NP. If you can solve a decision problem in polynomial time, then you can certainly verify a yes-answer in polynomial time by solving the problem directly.

P versus NP

The P versus NP problem asks whether every problem whose yes-solutions can be verified in polynomial time can also be solved in polynomial time. In symbols, it asks whether P = NP.

No proof of P = NP or P ≠ NP is known. The problem remains one of the Clay Mathematics Institute's Millennium Prize Problems. The difficulty is not that researchers have failed to find fast algorithms for only one isolated problem. Rather, an entire network of reductions connects many problems so that a polynomial-time breakthrough for one NP-complete problem would have consequences for all problems in NP.

The diagram places P and the NP-complete region inside NP. It is a conceptual picture: because P versus NP is unresolved, any drawing that separates P from NP should be understood as illustrating the widely studied possibility P ≠ NP rather than as a proof.

The Computerphile video above discusses P versus NP through popular-culture examples. Use it as a conversation starter, then return to the formal definitions in this course.

NP-Hardness and NP-Completeness

NP-Hard Problems

A problem H is NP-hard if every problem in NP can be transformed to H by a polynomial-time reduction of the required kind. NP-hardness is a statement about comparative difficulty. An NP-hard problem does not have to belong to NP, and it does not even have to be a decision problem.

This distinction is especially important with optimization. The shortest travelling salesperson optimization problem is NP-hard, while the bounded-length yes-or-no version is NP-complete.

NP-Complete Problems

A decision problem is NP-complete when two conditions both hold: it is in NP, and it is NP-hard. NP-complete problems are therefore the problems in NP that are at least as hard as every other problem in NP under polynomial-time reductions.

The Boolean satisfiability problem SAT was the first problem proved NP-complete. Other classic examples include 3-SAT, Hamiltonian cycle, clique, vertex cover, subset sum, and several graph-coloring decision problems.

Graph coloring gives a concrete classroom model. A decision version asks whether the vertices of a graph can be colored with at most k colors so that adjacent vertices receive different colors. For fixed k = 3, this decision problem is NP-complete.

Polynomial-Time Reductions

A polynomial-time reduction transforms instances of one problem A into instances of another problem B in polynomial time while preserving the yes-or-no answer. Written informally as A ≤p B, it means: if we had a polynomial-time algorithm for B, then we could use it together with the transformation to solve A in polynomial time.

The direction matters. To show that a new problem B is NP-hard, a standard strategy is to start with a known NP-hard or NP-complete problem A and reduce A to B. Reducing B to A would show that B is no harder than A, which is not the conclusion needed for NP-hardness.

A reduction is therefore not merely a conversion trick. It is a proof technique for comparing the computational difficulty of entire problems.

A Reduction Thought Experiment

Imagine that you can translate every instance of 3-SAT into a graph-coloring instance in polynomial time, with the property that the formula is satisfiable exactly when the graph can be colored using the required number of colors. If graph coloring also had a polynomial-time solver, then the translation plus that solver would yield a polynomial-time algorithm for 3-SAT.

The important evidence is not visual similarity between the two problems. The reduction must be computable efficiently and must preserve answers in both directions required by the equivalence of instances.

Beyond Exact Polynomial-Time Algorithms

When a problem is NP-hard, the correct practical response is not simply "give up." Real systems often use several strategies.

Approximation algorithms produce solutions provably close to optimal for suitable optimization problems. Heuristics search for good solutions without always guaranteeing optimality. Randomized algorithms use random choices. Parameterized algorithms can be efficient when a structural parameter is small even if the full input is large. Exponential-time algorithms can be engineered to handle moderate inputs far faster than naïve brute force. Special-case algorithms exploit structure that is absent from the most general formulation.

The 2-opt move above is a simple improvement step often used in travelling salesperson heuristics: replace two edges with two different edges when doing so shortens the tour. A heuristic can be highly useful even when it does not provide a proof of global optimality.

Complexity and Real-World Computing

Complexity theory helps explain why some scheduling, routing, verification, planning, and design tasks become difficult as data size grows. It also shapes algorithm engineering: recognizing an NP-hard core can redirect effort toward approximation, parameters, heuristics, or domain restrictions.

Complexity is also relevant to cryptography, but claims must be stated carefully. Modern cryptographic security usually depends on particular computational problems being difficult under particular attack models and input distributions. The unresolved P versus NP question is important background, but ordinary cryptographic security is not equivalent to the single statement P ≠ NP.

A Responsible Way to Read Complexity Claims

When you encounter a claim such as "this algorithm is efficient" or "this problem is impossible," ask several questions. What is the input size? What computational resource is being measured? Is the bound worst-case or average-case? Is the problem a decision, search, or optimization problem? Is the conclusion proven, conjectured, or only observed experimentally? What assumptions are being made about the model of computation?

These questions help prevent common mistakes such as treating Big O as a stopwatch measurement, calling every hard problem NP-complete, assuming NP means "not polynomial," or confusing "no fast algorithm is known" with "no fast algorithm exists."

Interactive Tasks

Quiz: Test Your Knowledge

What does computational complexity primarily study? (How computational resource needs grow with input size) (!How attractive a program interface looks) (!How many programming languages exist) (!How much a computer costs)

Which statement best describes the class P? (Decision problems solvable in polynomial time by a deterministic algorithm) (!All problems with exactly one solution) (!All undecidable problems) (!All problems requiring exponential memory)

Which statement best describes NP using certificates? (Yes-instances have certificates verifiable in polynomial time) (!Every instance can be solved in constant time) (!No instance can be verified efficiently) (!Every problem in the class is undecidable)

What relationship between P and NP is known? (P is contained in NP) (!NP is contained in P) (!P and NP are disjoint) (!P is identical to NP)

What remains unknown about P and NP? (Whether P equals NP) (!Whether P contains polynomial-time problems) (!Whether graphs can have vertices) (!Whether algorithms can use memory)

What two properties make a decision problem NP-complete? (It is in NP and it is NP-hard) (!It is in P and it is undecidable) (!It is exponential and randomized) (!It is recursive and linear)

Which direction is normally used to prove a new problem B NP-hard from a known NP-hard problem A? (Reduce A to B) (!Reduce B to A) (!Delete both problems) (!Run A and B only on tiny inputs)

Why is input encoding important in complexity analysis? (The length of the representation determines the formal input size) (!Encoding changes every problem into constant time) (!Binary encoding makes all algorithms polynomial) (!Input encoding eliminates the need for algorithms)

What is true about an NP-hard optimization problem? (It does not have to be a member of NP) (!It must be undecidable) (!It must have a linear-time algorithm) (!It must always be a decision problem)

Which statement about polynomial time is most accurate? (It is a central theoretical model of tractability but not a guarantee of practical speed) (!Every polynomial-time algorithm is fast on every real computer) (!Polynomial time means constant time) (!Polynomial time is always slower than exponential time)

Memory Game

Polynomial time	Running time bounded by a fixed power of input size
Certificate	Compact evidence used to support a yes-answer
Verifier	Algorithm that checks a proposed certificate
Reduction	Efficient transformation used to compare problem difficulty
NP-hard	At least as hard as every problem in NP under the chosen reductions
NP-complete	Both in NP and NP-hard
Heuristic	Practical method without a general optimality guarantee
Input size	Length or structural measure of the encoded problem instance

Drag and Drop

Match the correct terms.	Topic
P	Decision problems solvable in deterministic polynomial time
NP	Decision problems with polynomial-time verifiable yes-certificates
NP-hard	Problems at least as hard as every problem in NP under polynomial reductions
NP-complete	Decision problems that are both in NP and NP-hard
Reduction	Efficient transformation that transfers solutions between problem instances

Match every term first, then explain one pair aloud without using the exact wording from the table.

Crossword Puzzle

Polynomial	What type of time bound defines the class P?
Certificate	What is the compact evidence used to support a yes-instance in NP?
Reduction	What proof tool transforms one problem into another efficiently?
Verifier	What algorithm checks a proposed certificate?
Exponential	What growth type is represented by a function such as two to the power n?
Satisfiability	What property does SAT ask about a Boolean formula?

LearningApps

Cloze Text

Complexity analysis describes how resource use grows with

. A decision problem has a

answer. The class P contains problems solvable in

. The class NP can be characterized by certificates that are efficiently checked by a

. Every problem in P is also in

. A problem that is both in NP and NP-hard is called

. To prove a new problem hard, computer scientists often construct a polynomial-time

. The P versus NP problem is currently

. NP-hard optimization problems can still be approached using methods such as

. A practical algorithm should be judged by both asymptotic analysis and

.

Open-Ended Tasks

Easy

Growth Rate Poster: Create a one-page poster comparing O(1), O(log n), O(n), O(n log n), O(n²), and O(2^n). Include one invented example of an algorithmic task for at least four growth rates.
Runtime Mini-Experiment: Implement or simulate two simple algorithms with different growth rates, measure their running times for increasing inputs, and explain where the measurements agree or disagree with asymptotic expectations.
Complexity Vocabulary Video: Record a two-minute explainer that correctly distinguishes P, NP, NP-hard, and NP-complete using your own analogies.
Problem Classification Cards: Design a set of study cards for decision problems, search problems, optimization problems, certificates, verifiers, and reductions, with one example on each card.

Standard

Sorting Investigation: Compare two sorting algorithms theoretically and experimentally, then discuss how constants, input order, and growth rates influence observed performance.
Travelling Salesperson Lab: Generate small travelling salesperson instances, solve them by exhaustive search, count how the number of candidate tours grows, and identify when brute force becomes inconvenient.
Graph Coloring Interview: Interview a teacher, technician, scheduler, or software developer about a real allocation problem, model part of it as graph coloring, and evaluate where the model is useful or oversimplified.
Reduction Storyboard: Create a visual storyboard that explains the direction of a polynomial-time reduction from a known hard problem A to a new problem B and why reversing the arrow changes the conclusion.

Advanced

SAT Model Project: Encode a small scheduling or logic puzzle as a Boolean satisfiability instance, explain each variable and clause, and verify one satisfying assignment.
Approximation and Heuristics Study: Choose an NP-hard optimization problem, implement or analyze one heuristic or approximation method, and compare solution quality with exact solutions on small instances.
Complexity Claim Fact Check: Find three public claims about algorithmic difficulty, trace each claim to reliable technical sources, and label it as proven, conditional, open, or merely empirical.
Mini Research Seminar: Prepare a ten-minute seminar on one advanced topic such as PSPACE, parameterized complexity, randomized complexity, or approximation hardness, and connect it explicitly to P and NP.

Learning Assessment

Algorithm Comparison Assessment: Given two algorithms with different asymptotic bounds and realistic constants, decide which you would choose for several input sizes and justify where asymptotic reasoning does and does not settle the decision.
Certificate Design Assessment: For a proposed decision problem, design a certificate format and a verifier, then argue whether the verification procedure runs in polynomial time.
Reduction Reasoning Assessment: Analyze a proposed reduction proof, identify the direction of the transformation, test whether yes-instances and no-instances are preserved, and decide whether the claimed NP-hardness conclusion follows.
Decision versus Optimization Assessment: Convert a small optimization problem into a threshold decision problem and explain how an algorithm for one version could help with the other.
P versus NP Consequences Assessment: Compare the hypothetical worlds P = NP and P ≠ NP, separating statements that logically follow from the equality from broader claims that would still require additional assumptions.
Practical Strategy Assessment: Given an NP-hard planning problem with a small parameter and a strict time limit, propose a combination of exact, heuristic, approximation, or parameterized methods and defend your design choices.

Evidence of Learning

Evidence of learning should show more than vocabulary recall. A strong portfolio demonstrates all four areas below.

Knowledge Evidence: Accurate explanations of input size, asymptotic growth, P, NP, NP-hardness, NP-completeness, and polynomial-time reductions.
Reasoning Evidence: Correct use of reduction direction, careful distinction between proof and conjecture, and justified comparisons of algorithmic growth.
Skill Evidence: Ability to analyze pseudocode, conduct timing experiments, model a problem as a graph or formula, and communicate results clearly.
Product Evidence: At least one polished artifact such as a poster, program, model, video, research note, or presentation that makes complexity ideas understandable to another learner.
Transfer Evidence: Ability to recognize complexity issues in a new context such as scheduling, routing, verification, planning, or data processing and propose an appropriate computational strategy.

OERs on the Topic

The English Wikipedia article below can be used as an open reference for definitions, historical context, and links to more specialized topics. Compare any advanced claim with additional reliable sources when preparing assessed work.

Linked Learning Areas

Computational complexity connects mathematical proof with practical algorithm design. The navigation table below highlights the most useful neighboring topics for further study.

Computational Complexity