Computation & Complexity

What can computers actually do - and what can't they?

Junior level — plain language, no maths

Computers look unstoppable - they land rockets, crush grandmasters at chess, paint photorealistic scenes from a sentence. So here's a genuine jolt: there are problems that no computer, however fast or huge or cleverly coded, will ever solve. Not because we haven't built the right machine yet, but because it is mathematically impossible, full stop.

Alan Turing proved this in 1936 - before real computers even existed. No program can be written that reliably decides whether any given program will eventually finish or loop forever. It's called the Halting Problem, and it's provably unsolvable. Turing's trick was pure logic: if such a checker existed, you could aim it at itself and manufacture a contradiction, exactly like the sentence "This statement is false."

Past what's impossible sits the question of what's merely hard. Sorting a list takes milliseconds; finding the shortest tour through 1,000 cities seems to demand trying a staggering number of combinations, hopeless even for a supercomputer. The biggest open question in computer science - and one of the great unsolved problems in all of mathematics - is whether those hard problems are truly hard, or whether we've just been too slow to spot a shortcut. That's P vs NP, and there's a $1,000,000 prize waiting for whoever settles it.

Turing machines, decidability, and the complexity zoo

Student level — the core equations

A Turing machine is computation stripped to the bone: an infinite tape, a head that reads and writes one square, and a handful of states with rules \(\delta(\text{state}, \text{symbol}) \to (\text{state}', \text{symbol}', \text{move})\). It looks absurdly primitive, yet the Church–Turing thesis holds that anything computable at all is computable by one of these. And a single Universal Turing Machine, handed the description of any other, can imitate it perfectly - the theoretical seed of every general-purpose computer you've ever used.

Turing's Halting Problem falls out by diagonalisation. Suppose a decider \(H(M, w)\) could always say whether machine \(M\) halts on input \(w\). Build a spoiler \(D(M)\) that runs \(H(M, M)\) and then does the opposite - loops if \(H\) says "halts", halts if \(H\) says "loops". Now feed \(D\) its own description: \(D(D)\) halts exactly when it doesn't. Contradiction, so \(H\) can't exist. Rice's theorem generalises the damage: every non-trivial question about what a program does is undecidable, which is why perfect automatic bug-checking is off the table.

Among the problems that are solvable, we sort by cost. P is everything decidable in polynomial time; NP is everything whose answer, once guessed, can be checked in polynomial time - Sudoku, graph colouring, factoring. A problem is NP-complete if it's in NP and every other NP problem reduces to it, so it's as hard as the whole class at once. Cook and Levin (1971) proved boolean satisfiability (SAT) is one such problem, and thousands of everyday problems have since joined it. Crack any one of them efficiently and you've proven \(P = NP\) - and cracked them all.

Circuit complexity, randomised computation, and the limits of proof

Scholar level — full mathematical depth

01P vs NP as a question about circuit size

One promising angle on \(P\) vs \(NP\) reframes it in hardware. Any computation can be laid out as a Boolean circuit - a graph of AND, OR and NOT gates - and its cost is the gate count. Everything in \(P\) has polynomial-size circuits, so if you could prove some \(NP\) problem needs superpolynomially many gates, you'd separate the classes. The plan is clean; the execution has proven brutal.

02Hard functions exist - we just can't point to one

Curiously, we know hard functions are everywhere. A simple counting argument (Shannon) shows almost every Boolean function on \(n\) bits needs a circuit of size \(\Omega(2^n/n)\) - astronomically large - so the vast majority of functions are hard. The catch is that the argument is non-constructive: it proves hard functions abound without naming a single one. For explicit functions in \(NP\), the best lower bounds anyone has proven remain near \(\Omega(n \log n)\), a laughable distance from exponential. We are surrounded by hard problems and can prove almost none of them hard.

03The natural-proofs barrier

Worse, there's evidence the obvious strategies can't work. Razborov and Rudich (1994) showed that any "natural" proof - one that's constructive and applies to most functions, as nearly all circuit arguments do - would, if it proved strong lower bounds, also hand you an algorithm to break cryptographic pseudorandom generators. So a natural proof of \(P \ne NP\) would destroy the very one-way functions modern cryptography assumes exist. The tools that feel obvious are provably too blunt.

04The other walls: relativisation and algebrisation

Two more barriers hem the field in. Most classical techniques relativise - they'd still work if every machine had a magic oracle - yet there exist oracle worlds where \(P = NP\) and others where \(P \ne NP\), so no relativising proof can decide it. The algebraic methods that cracked \(IP = PSPACE\) dodge that but hit the later algebrisation barrier. Between them, three barriers rule out essentially every method we currently have - which is why a resolution would need a genuinely new idea, not a sharper version of an old one.

05Is randomness actually necessary?

A different thread asks whether coin flips add real power. BPP is what you can solve in polynomial time allowing a small two-sided error, and for decades it seemed strictly richer than \(P\). The surprise (Impagliazzo–Wigderson, 1997) is that it probably isn't: if suitably hard functions exist, then \(BPP = P\) and every randomised algorithm can be derandomised. Hardness, the villain of the P-vs-NP story, turns out to be exactly what you'd need to make randomness redundant.

06Interactive proofs and a shock from 2020

Let a verifier interrogate a prover and computation's reach expands astonishingly. Shamir proved \(IP = PSPACE\): anything solvable in polynomial memory can be verified through conversation. Add multiple provers sharing quantum entanglement and it explodes all the way to \(MIP^* = RE\) (Ji et al., 2020) - the entire class of recursively enumerable problems, including undecidable ones. That result didn't just startle complexity theorists; it settled Connes' embedding conjecture in pure operator algebra, a reminder that the theory of computation now reaches into the far corners of mathematics.