The Absolution by Jonathan Holt Read Free Book Online

problems. Put simply, it asked whether there was an algorithm that would allow a computer to find answers to complex mathematical problems as quickly as it could check them.
    Aware that even a simple statement like that might go over the heads of some of his readers, he gave a real-world example.
    Suppose you want to go to Disney World, and you know there are long queues for the most popular rides. So you try to work out a route that will cut your waiting time to a minimum. There are 21 attractions on the One-Day Touring Plan – that’s 51,090,942,171,709,440,000 possible itineraries, six times as many as the estimated number of grains of sand in the world.
    But here’s the thing. If you generate two itineraries, and you know the estimated wait at each ride, you can very quickly see which one is better. In other words, the solution is easy to check. Why can’t we devise a computer program that can work out the best itinerary just as easily? At the moment we can only generate solutions one by one and then compare them – what’s sometimes called a “brute force” program, a fancy name for trial-and-error. When the number of possible solutions is as big as 21 factorial, as it is in the Magic Kingdom example above, that would take longer than a human lifetime, even for a computer.
    A seating plan is just another version of the same problem. Let’s say you have fifty couples coming to your wedding, and each table seats ten people. How do you break those couples up so everyone’s sitting next to someone who isn’t their partner? And – let’s complicate it – how do you simultaneously make sure that every couple from the groom’s side sits on a table with at least one couple from the bride’s side? Then let’s say the groom has invited all fifteen members of his rugby team, who tend to get drunk and sing rude songs if they’re placed on the same tables . . . People usually figure out an acceptable solution to these kinds of problems, because it’s pretty easy to see when you’ve got it right. But why isn’t it possible to write an algorithm that will do it for you?
    An algorithm isn’t magic – it’s just a set of instructions for carrying out a calculation. You used an algorithm every time you did long multiplication at school. But in the examples above, no one has ever found an algorithm that would allow a computer to generate an answer in what mathematicians call polynomial time, or P – that is, an amount of time that isn’t ridiculously long.
    The point is, if such an algorithm did exist, it would revolutionise the kinds of tasks we ask computers to carry out. We could use machines to solve every remaining mystery of our existence, from why a wave breaks where it does to how a jet vapour trail over New York affects the chances of rain in London. Itwould mean that computers could scan every detail of our personalities and find the one person in the world most likely to be our soulmate. It would mean that instead of needing an infinite number of monkeys and an infinite number of typewriters to come up with the works of Shakespeare, a computer could generate plays that were Shakespearean in every respect other than the actual authorship. It would even mean, in theory, that Amazon could write books specially for you, based on your favourite passages and characters in other authors’ works. Or, on a more altruistic level, it would mean that if you had fifty kidney donors and fifty people on dialysis, you could find the most efficient match between them in seconds.
    And it would mean – perhaps ironically – that encrypted websites like Carnivia or PayPal would be in real trouble, since hackers would quickly be able to generate the private keys on which such sites depend.
    Many people, it has to be said, think that a world in which P equals NP would be a more sterile, less interesting place; one where creative leaps,