P = NP (And Some Basic Computer Science)

The computer science and maths problem P = NP is one that many people have heard of, mostly because a $1,000,000 prize has been offered for a solution (that's right, though this is probably the hardest way imaginable to become a millionaire!). The Clay Mathematics institute named it as one of their seven 'Millennium Prize Problems', and as such it has gained a certain notoriety. Another, less provable but I think equally true reason it is famous is because its name ( ie. P=NP) is not difficult to remember, at least compared with other such problems (eg. Navier - Stokes existence and smoothness). But anyway, onto the maths:

P=NP is a problem to do with the complexity of certain questions that can be solved by computers. Say you wanted to write a program that would give you all the even numbers from a set of numbers that you give it. For example, say you give it x numbers. For each number, it would divide by 2 and then if there is no remainder, the program tells you the number is even. Therefore, for each number, the program takes one step to 'solve' it, and then moves onto the next number. The running time for this program is therefore x steps. However, if you wanted all the numbers which are not divisible by 2 or 3, then the same program would take 2 steps per number, giving a running time of 2x.

Now this is a simplistic introduction to the concept of 'running time', and by extension 'complexity'. However, running time is not the same as complexity. If you gave the 'even number program' described above 10¹⁰⁰ numbers, it would have a very long running time (10¹⁰⁰ steps). However, complexity is about the equation which gives us the running time. In the case of our even number program, the running time = X steps, with X being the number of input numbers. This is considered an 'easy' problem.

Now some problems have a complexity equation that is a polynomial (ie. the sum of powers of x). These problems are considered 'easy' as the running time increases relatively slowly as x increases. Other problems do not, and rather have a complexity equation that is an exponential function (eg. 2^x). These problems are considered 'hard' as the running time increases very quickly as x increases (see how big 2¹⁰ is, and then 2¹⁰⁰ if you don't believe me).

So where does P=NP fit into all this computational complexity theory? Well P-problems (or Polynomial problems / easy problems) and NP-problems (Not Polynomial problems / exponential problems / hard problems) both exist, and P problems are a subset of NP problems (ie. all 'easy' problems have ways of solving them which are 'hard', but not all 'hard' problems have ways of solving them which are 'easy'). 

Once the problem is solved however, another problem to verify the solution arises, and this second problem is also either 'easy' or 'hard'.

P=NP states that all problems that can be verified in polynomial time (ie. the second problem is 'easy') can also be solved in polynomial time (ie. the first problem has an 'easy' way of solving it, even if people don't know how yet). For example, if you make a program that, given a set of integers, finds if some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer "yes, because {−2, −3, −10, 15} add up to zero" can be quickly verified with three additions (three steps). However, there is no known algorithm to find such a subset in polynomial time (there is one, however, in exponential time, which consists of 2ⁿ-1 steps) (Source of Example: Wikipedia)

P=NP would state that there must exist an algorithm to find the subset in polynomial time, as all problems that can be verified 'easily' can also be solved 'easily'.

There is great debate as to whether P=NP is true, with many mathematicians and computer scientists working on the project. The current majority lies in the P does not equal NP camp, who believe there exist problems that can be difficult to solve but easy to check (like the one above), but more than enough believe that P does indeed equal NP. A proof either way would have huge practical and theoretical implications in many fields including, of course, mathematics which is why this is hailed as one of the most important problems of the modern age. Any takers?