SLIDE 1 / 10
CSZone.co.uk
Click anywhere to advance · Arrow keys also work
AQA 7517 · Paper 1 · 4.4.4b

P vs NP &
Intractability

Complexity classes · NP-complete · Tractable vs intractable · Section 4.4

WHAT YOU'LL LEARN
Class P · Class NP · NP-complete · Tractable vs intractable · TSP example
AQA SPEC LINK
4.4.4 — Complexity classes P and NP
Class P

Class P — Polynomial Time

Class P contains problems that can be solved in polynomial time O(nᵏ) for some constant k. These are considered tractable.
Polynomial time: O(n), O(n²), O(n³)… time grows as a power of n
Examples: sorting (O(n log n)), searching (O(log n)), shortest path (Dijkstra's)
P problems are practically solvable even for large inputs
Class NP

Class NP — Nondeterministic Polynomial

Class NP contains problems where a proposed solution can be verified in polynomial time, even if finding the solution may take much longer.
Key distinction: NP = verifiable in polynomial time (not necessarily solvable in polynomial time).

Example: Sudoku — verifying a solution is fast (check rows/cols/boxes); finding a solution is hard.
P vs NP Question

The P = NP Question

Does P = NP? Is every problem that can be verified quickly also solvable quickly?
This is the biggest unsolved problem in computer science and mathematics
Most experts believe P ≠ NP — that some NP problems are genuinely hard to solve
A proof either way would be one of the greatest mathematical discoveries in history
The Clay Mathematics Institute offers $1 million for a solution
NP-Complete

NP-Complete Problems

An NP-complete problem is in NP AND every other NP problem can be reduced to it. If any NP-complete problem is in P, then P = NP.
Travelling Salesman Problem (TSP) — find shortest route visiting all cities exactly once
Satisfiability (SAT) — can boolean variables be set to satisfy a formula?
Graph colouring — can vertices be coloured with k colours so no adjacent vertices share a colour?
Tractable vs Intractable

Tractable and Intractable Problems

CategoryDefinitionExample
TractableSolvable in polynomial time (in P)Sorting, searching, Dijkstra's
IntractableNo polynomial algorithm exists (exponential or worse)TSP (exact), SAT in general
UncomputableNo algorithm exists at allHalting problem
For TSP with n cities, brute force is O(n!) — 20 cities = 2.4 × 10¹⁸ routes. Completely impractical.
TSP Example

Travelling Salesman Problem (TSP)

Given n cities and distances between them, find the shortest route that visits every city exactly once and returns to the start.
For n=5 cities: 4! = 24 possible routes (feasible)
For n=20: 19! ≈ 1.2 × 10¹⁷ routes (infeasible)
Real-world applications: delivery route optimisation, circuit board drilling
Approximation algorithms give near-optimal solutions in reasonable time
Approximation

Dealing with Intractable Problems

Approximation algorithms — find a near-optimal solution quickly (e.g. within 2× optimal)
Heuristic methods — e.g. greedy nearest-neighbour for TSP
Restrict problem size — solve exactly only for small n
Use special structure — some instances of NP problems have polynomial solutions
AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style
(a) Explain the difference between a problem in class P and a problem in class NP. [2]
(b) Explain what is meant by an "intractable" problem, giving an example. [2]
(c) Explain what is meant by "NP-complete". [2]
[6 marks]
2 marks
(a) P: can be solved in polynomial time. NP: solution can be verified in polynomial time (but may not be solvable in polynomial time)
2 marks
(b) Problem with no known polynomial time solution — exponential time required, making it impractical for large inputs. Example: Travelling Salesman Problem
2 marks
(c) A problem that is in NP AND every NP problem can be reduced to it in polynomial time. If any NP-complete problem is solved in polynomial time, then P=NP
Summary

Key Points to Remember

Class P — solvable in polynomial time; tractable problems
Class NP — solution verifiable in polynomial time; may be hard to solve
P = NP? — greatest unsolved problem in CS; most believe P ≠ NP
NP-complete — hardest problems in NP; TSP, SAT, graph colouring
Intractable = no polynomial solution; exponential time makes them impractical
🎉 Lesson complete — move to the quiz!