Start here

The whole problem in one idea

Think about a jigsaw with a thousand pieces. Finishing it can take a whole weekend. Checking a finished jigsaw takes one look. Passwords are the same. Guessing someone's password could take years. Checking a guess takes a second.

That gap is the whole of P versus NP. Some answers are quick to check but seem very slow to find. The big question is simple to say. Is the gap real? Perhaps every problem with quick-to-check answers also hides a quick way to find them, and we just have not spotted it. Nobody has proved it either way. Not in more than fifty years of trying.

The delivery driver

Picture a delivery driver in Liverpool. She has to visit ten cities and get home by dark. Which order gives the shortest trip? With ten cities she could try every route and pick the best.

Now give her two hundred cities. The number of possible routes is bigger than the number of atoms in the universe. Every computer on Earth, running until the sun burns out, could not try them all. Here is the sting. Nobody knows a clever shortcut. Nobody has proved there is no shortcut either. This is called the travelling salesman problem, and it sits at the heart of the whole subject.

The wedding seating plan

Now plan a wedding. There are 150 guests and one long table. Some relatives loathe each other, and they must not sit side by side. Checking a plan is easy. Walk round the table, look at each pair of neighbours, and you are done in minutes. Finding a plan is the monster. With only 100 guests there are more possible seatings than there are electrons in the solar system.

Here is the twist that makes this famous. Say a bad pairing costs a million pounds and a happy pairing costs a penny. Can you seat everyone for about a pound? That is the driver's problem in a posh frock. Find the cheapest route round the table. Crack the wedding and you crack the salesman too. Thousands of hard problems turn out to be one problem wearing different clothes.

The cliff edge

The strangest part is how thin the line is. Take a group of people and split them into pairs, so that each pair gets on. That sounds huge, but it is easy. A clever method has been known since the 1960s, found by Jack Edmonds.

Now change one word. Split the same people into threes, so that each three gets on. That tiny change turns an easy job into one of the hardest problems known. Two is easy. Three is a cliff edge. Nobody can fully explain why the cliff is there.

Why it matters

Your bank card is safe online because one of these problems is slow. If someone found a fast method, they could read secret messages and crack the codes that guard your money.

School timetables, delivery routes and exam seating are all in the same family of problem. So is DNA sequencing, where scientists piece tiny fragments into one long strand. The Clay Mathematics Institute has offered a million dollars for a proof either way. It is one of seven great prize problems, and the prize has waited unclaimed since the year 2000.

What nearly everyone believes, and why we keep score

So what do the experts think? In 2012 there was a poll. About 80 per cent of those who answered said P is not NP. In plain words, they believe the gap is real, and some answers really are harder to find than to check. Donald Knuth, one of the most famous names in computing, joked that whoever proves P equals NP should get one extra prize from him: one live turkey.

Yet people keep claiming proofs. Gerhard Woeginger kept a public list of these claims from 1996 until 2016. His list holds 116 entries. We have found 43 more candidates since his list froze.

Here is the honest bit. For 100 of the 116 old entries, the record shows no expert verdict either way. That is 86.2 per cent. No verdict does not mean a claim was accepted. It means nobody wrote down whether it was right or wrong. There is rot too. Of the 174 web links in the old list, 45 are now dead. Papers vanish. Pages rot.

Someone should keep honest score, and that is why this register exists. It carries his page forward. We keep his own notes with every entry. We check the links. We write every change in a ledger that keeps its full history. We record claims, never judgments of the people who make them.

Where to go next

Want to hear all this instead? The best listen for beginners is the BBC radio episode In Our Time on P versus NP, from November 2015. As one guest put it, the whole question is whether “things that are easy to check are actually easy to find”. Three experts and a host untangle it in about 45 minutes, and no maths is needed.

Here is where to go next on this site.

• The register holds all 116 of the old entries, with sources and status for each.
• Test your proof is for anyone who thinks they have cracked it. It sets out the known barriers as simple questions you can ask of your own work, before you claim.
• The stats show the numbers behind this page as charts, old claims and new. Every figure is dated and sourced.

Welcome in. The problem is hard. The door is open.