Complexity theory asks how hard a problem is for every possible algorithm
In short: Asking whether a tour of Germany's 14 biggest cities can be done in under 2,000 kilometres is one question. Asking how hard that kind of question is in general, no matter which method anyone ever invents, is another. Computational complexity theory tackles the second, and its most famous open puzzle, P versus NP, carries a Millennium Prize.
The field sorts problems by the resources they demand, chiefly running time and memory, though it also counts things like messages exchanged, logic gates in a circuit or processors working in parallel. It differs from the analysis of algorithms, which measures one specific method, and from computability theory, which only asks whether a problem can be solved at all with unlimited resources.
A crucial distinction is between a problem and an instance of it. Checking whether 15 is prime is an instance, with the answer no; primality testing is the problem. Knowing the answer for the German road trip tells you nothing about a 10-kilometre round trip through 14 sites in Milan, so theorists study whole problems. Inputs are encoded as strings of 0s and 1s, with care taken that the choice of encoding does not change the verdict. Many questions reduce to yes-or-no form; even multiplying two numbers can be recast as checking whether a given triple of numbers fits.
Difficulty is measured by how the worst-case running time grows as the input gets longer. If it grows no faster than some polynomial, the method runs in polynomial time, and Cobham's thesis proposes that exactly these problems are realistically solvable.
The standard yardstick is the Turing machine, simple enough to analyse yet believed as powerful as anything else, from a supercomputer to Conway's Game of Life. Variants add random bits, quantum behaviour or non-determinism, the ability to branch into many paths at once and succeed if any branch does. Such a branching machine cannot actually be built. All these variants solve the same problems in principle, but once time or memory is capped some may pull ahead of others.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Computational complexity theory
To cite this card, link to https://intellectplus.co.uk/app/science-computational-complexity-theory.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Discrete mathematics · More in Science · Latest · A–Z · All topics