Tractable and Intractable Problems for GCSE Computer Science

What does "polynomial time" mean?

The running time of an algorithm is described using Big O notation, which captures how time grows relative to input size n. An algorithm is considered efficient if its time complexity is polynomial — that is, expressible as n raised to some fixed power.

Notice the dramatic difference between polynomial and exponential growth. For n = 100, an O(n²) algorithm takes 10,000 steps — manageable. An O(2ⁿ) algorithm would take more steps than there are atoms in the observable universe.

What makes a problem tractable?

A problem is tractable if there exists an algorithm that solves it in polynomial time — O(n), O(n²), O(n log n), and so forth. The key word is exists: we do not need to have already written the algorithm, just to know one is theoretically possible.

Examples of tractable problems:

• Sorting a list (merge sort runs in O(n log n)).
• Searching a sorted list (binary search runs in O(log n)).
• Finding the shortest path in a weighted graph (Dijkstra's algorithm runs in O((V + E) log V)).
• Multiplying two matrices together.

These problems scale well: doubling the input roughly doubles, quadruples, or at most octiples the work.

What makes a problem intractable?

A problem is intractable if the best known algorithm runs in superpolynomial (typically exponential or factorial) time. As input grows, the time required increases so rapidly that no realistic computer can handle anything beyond a very small input.

The classic example is the Travelling Salesman Problem (TSP): given n cities, find the shortest route that visits every city exactly once and returns to the start.

• For n = 5 cities, there are 12 possible routes — easy to check.
• For n = 20 cities, there are roughly 60 billion routes.
• For n = 100 cities, the brute-force route count exceeds 10¹⁵⁷.

No supercomputer could enumerate all routes for 100 cities in the lifetime of the universe. The TSP is intractable by brute force.

What is the P vs NP question?

Two important classes of problem exist in theoretical computer science:

• P — problems solvable in polynomial time. If a problem is in P, an efficient algorithm exists.
• NP — problems whose solutions can be verified in polynomial time, even if finding them may not be efficient. Every P problem is also NP (checking is easier than solving), but whether NP = P is the most famous unsolved problem in computer science.

The significance: if P = NP, every problem whose answer can be quickly checked could also be quickly solved. This would have profound implications for encryption (most public-key schemes rely on NP-hard problems being hard to solve).

At GCSE, you are not expected to prove P ≠ NP. You need to understand the distinction between tractable and intractable problems, and know that intractable does not mean impossible — only that no polynomial-time algorithm is currently known.

How do computers deal with intractable problems?

Since exact solutions are impractical, two approaches are common:

1. Heuristic algorithms — find a "good enough" solution quickly rather than the optimal solution. For TSP, the "nearest neighbour" heuristic visits the closest unvisited city at each step. The result is often near-optimal but not guaranteed to be the shortest route.

2. Approximation algorithms — produce a solution guaranteed to be within a known factor of the optimal answer. For example, a 2-approximation for TSP guarantees a route no more than twice the minimum possible length.

What are real-world examples of intractable problems?

• Protein folding — predicting the 3D shape of a protein from its amino-acid sequence. Vital for drug design; recently partly addressed by AI heuristics (AlphaFold).
• Circuit board routing — laying out connections on a complex printed circuit board with no crossings.
• Exam timetabling — scheduling exams so no student has two at once, given thousands of students and hundreds of modules.
• Cryptography — integer factorisation (splitting a large number into primes) is believed to be intractable, which is why RSA encryption is secure.

Frequently asked questions

Is the Travelling Salesman Problem unsolvable?

No — the TSP is unsolvable only by brute force for large inputs. Small instances (fewer than about 20 cities) can be solved exactly. For larger instances, heuristic and approximation algorithms find high-quality solutions in practical time. The distinction is between finding the provably optimal answer (intractable for large n) and finding a very good answer quickly (tractable).

Do I need to understand P vs NP for my GCSE exam?

You need to understand the concept at a qualitative level: tractable problems have polynomial-time solutions; intractable problems do not. You should know examples of each and understand why heuristics are used for intractable problems. A detailed mathematical treatment of P = NP is not required at GCSE.

Can a faster computer make an intractable problem tractable?

Not in practice. Even if a computer were a trillion times faster, an O(2ⁿ) algorithm for n = 300 would still take longer than the age of the universe. The problem is with the algorithm's growth rate, not with hardware speed. Intractability is a fundamental property of the problem, not a temporary engineering limitation.

Why is intractability important for encryption?

Many encryption schemes — including RSA, used to secure HTTPS connections — rely on the practical intractability of factorising very large numbers. If an efficient (polynomial-time) algorithm for factorisation were discovered, current public-key cryptography would be broken instantly. This is why the P vs NP question matters far beyond academic theory.

---

Struggling with Big O notation or algorithm complexity? Professor Turing at aitutors.me can work through concrete examples until the concept clicks.