WITH the European football season halfway through, fans are wondering whether
their team has even a mathematical chance of winning the league. But don’t try
working it out, warn Dutch researchers, as it’s one of the toughest problems
around.
Mathematicians class the difficulty of a problem according to the time it
takes to solve it. Among the most difficult are NP-hard problems, for which the
time increases exponentially with the problem’s size.
The most famous example is the travelling salesman problem: given a number of
cities and the distance between them, what is the shortest route that visits
them all…
