Complexity theory asks how hard a problem is for every possible algorithm
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.
Source: Computational complexity theory
