P vs NP
The Millennium Prize Problems are a collection of seven previously unsolved problems from different areas of mathematics which were collected together and set on the year 2000, although some have been around for centuries. Each have a prize of $1,000,000 and in the 16 years since the launch only one has been solved. I want to do a series of articles explaining the current state of each of the problems in as simple a way as possible, starting with the computing theory problem: P vs NP. The emphasis for all of these will be trying to make these highly conceptual problems understandable to a layperson as far as it is possible.
Some problems are hard to solve and yet if they have already been solved they are easy to check that their solution is true. For example, imagine you have a 1,000 piece jigsaw made up of entirely white pieces; it is clearly going to be very difficult to solve. If, however, you find it already completed then checking it is trivial. You could look at the connection between each pair of pieces (typically there about 1935 of these connections) and just check that they were indeed fitted properly together. What P vs NP states is that for each problem which can be checked easily once you have a solution, there exists some algorithm that would have been able to solve it in a quick time, if you were sufficiently clever about it. This is a slight simplification of the real problem, but it is the central idea.
Putting a little more rigour in, P refers to problems can be completed in polynomial time. So as the list of elements that you are working on, n grows, the completion time is proportional to some finite polynomial in n. NP is the next class up of complexity but it is just about possible still that every problem in this category is actually solvable in polynomial time.
The prize money is available for anyone who can prove either that it is true (which almost everyone believes isn't true) or that it is false to which the counter example is proving surprisingly elusive. Of all of the Millennium Prize Problems P vs NP is the one with the most submissions; every year dozens of false proofs are entered, many of them by crazy people. However there are a few attempts by serious computing complexity experts every year, but so far they have all been flawed. I've learned to look at news of the problem’s completion with heavy sceptism since it happens so often.
While we expect P vs NP to be false, I think I'm not alone in secretly hoping that it is true. To still have the potential that all of these difficult problems could still have a better solution is alluring as a hope. There have problems in the past that have had almost everyone assume the result one way and find themselves proved wrong centuries later. For example, there are some numbers with have an even number of primes in their prime factorisation e.g. 6=2*3 which is two primes. Let's call such numbers peven. Similarly, some numbers such as 12=2*2*3 has an odd number of primes so we'll call it podd. 1 is an honorary peven number because it has 0 prime factors.
Let's define the function E(n) to be the number of peven numbers up to an including n, while O(n) is the number of podd numbers up until that same point. As soon as you get to n=2 then O(n)>E(n) for instance for n=7, the podd numbers are 2, 3, 5 and 7, while the peven numbers are 1, 4 and 6; so O(7)=4>E(7)=3. As you carry on the lead of the podd numbers gets bigger and bigger and it was assumed that the pevens would never catch up. When Polya (see Lost in Space) came up with this conjecture he tested it for the first 1500 and later others checked the first million numbers. However in the 1960s we finally found a counterexample and the first one occurs when O(906180359)<E(906180359). This is exactly why we prove things.
The rest of the Millennium Prize Problems to follow.
