快猫短视频

WITH the European football season halfway through, fans are wondering whether
their team has even a mathematical chance of winning the league. But don鈥檛 try
working it out, warn Dutch researchers, as it鈥檚 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鈥檚 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 once? The only way to solve it is by measuring every possible route and
finding the shortest, a task that increases exponentially with the number of
cities.

Working out whether a team can win its league turns out to be mathematically
identical to the travelling salesman problem, say Walter Kern and Dani毛l
Paulusma of the University of Twente. The problem can be solved quickly when
only a small number of teams are involved, such as when a team is near the top
of the table. This is equivalent to a travelling salesman problem with only a
few cities. 鈥淏ut the task is much more difficult when your team is in the lower
half of the table and a lot more teams are involved,鈥� says Kern.

Fans had a much easier time in the days when teams got 2 points for a win and
1 for a draw. Kern and Paulusma have shown that this is mathematically simpler
than a travelling salesman problem, and the time to solve it increases more
slowly as it gets bigger. The switch a few years ago to 3 points for a win
turned it into an NP-hard problem.

The Football Association in London is unfazed. 鈥淚 suppose you could argue
that it adds a little more spice to the game,鈥� says a spokesman.