P versus NP

by Reetobrata Chatterjee

Introduction

P versus NP is a major problem in Computer Science. It is one of the 7 Millennium Prize problems, which are widely regarded as the most important problems in Mathematics of the generation (and by extension into fields such as Physics and Computer Science). Arguably, the P versus NP problem is one of the most important of these problems, because of the major real world implications of a proof such as this. Why should you care? If you are clever/lucky enough to solve this problem, you’ll net yourself a cool $1,000,000, which may not be as good as £1,000,000, but is a pretty hefty sum for solving a Maths problem. Also, you are quite likely to receive the Turing Award and/or the Fields Medal, each regarded as the highest honour in the fields of Computer Science and Mathematics respectively.

The Problem

The problem itself is quite simple to understand informally. It asks whether the solution to a problem of some description can be determined “quickly”, if its solution can be verified quickly. It may be necessary to mention computers, since this IS a problem in Computer Science, but it’s more general than that. This statement, if proved either way, would apply to any problem solved by algorithmic thinking, i.e. following a sequence of steps, sort of like a cooking recipe, and seeing how fast you can get to the end.

An example of such a problem is factorising numbers into its prime factors. In order to simplify this slightly, I’ll assume that the number only has 2 prime factors, although more generally, it would apply to any such problem.

Take the number 15. It is simple to see that the factors are 3 and 5. Also if the numbers 3, 5 and 15 were given, it would be easy to check that 3 x 5 = 15. However, the factorisation was not actually done algorithmically, since most people will KNOW when they see 15 that 3 x 5 = 15. In order for the process to be algorithmic, it has to go about finding the factors in a methodical way. A simple example would be checking from 2 onwards whether the number divides into 15 exactly and giving the result when it does. This is how a computer would do it.

The reason an algorithmic approach is necessary is because for bigger numbers, most people wouldn’t instinctively know the factors. Take the number 1065023. Not so easy now is it. However, the computers method would still work – starting a 2 and checking each number in turn. It is much slower for the number 1065023 than 15, because it is bigger. In fact if this algorithm was used, it is exponentially slower – for each number all the numbers up to sqrt(the_number) would have to be checked.

Now what if I told you to check the numbers 1031 and 1033? Using pen and paper (or more likely a calculator), it would come out to be the right answer. Although this process was slower than checking 3*5, it is much faster than trying to find the factors in the first place. This is essentially the dilemma which P versus NP tries to address. Is there a quick way to find the factors, since if given the factors the answer can be checked quickly?

The Actual Problem

If the actual problem was this simple, there would probably be no money left to claim. The actual problem is just a little bit harder:

1)      It’s more general – it should apply to EVERY problem which can be approached algorithmically with quickly verifiable answers, not just a particular case such as prime factorisation. There are infinite amounts of these problems.

2)      Showing the solution works for a certain input is not enough – it should apply to every input to the problem which can be entered into a problem, i.e. an example is not enough, a mathematical proof is necessary

Still with me? Great here[hyperlink to http://www.claymath.org/sites/default/files/pvsnp.pdf]’s the actual statement of the problem.

Implications

If P ≠ NP, noting much would change, except that banks and every other website in the world could breathe a sigh of relief since there encryption system would be proven safe. At least until the next threat.

The implications of P = NP however are slightly more exciting:

·     All the security measures of the internet would probably have to be redone. Current encryption relies on large numbers being difficult to factorise – that would not be the case anymore.

·     

Almost everything would be more efficient. The Post Office, Amazon and all other companies which deal with logistics would be able to maximise efficiency. Problems such as the Travelling Salesman problem, which are typically very difficult to solve, could be easily solved, leading to cheaper deliveries and services.

·     In areas such as Machine Learning, Artificial Intelligence and Computer Vision, most things would become perfect. AI would be that much closer to taking over the world, since it would be able to quickly learn and adapt through the new algorithms that would be made available.

·     

    All the other Millennium Prize problems would become much easier to solve, since their proofs could be condensed.

Conclusion

This is a very important problem. P = NP could change the world; P ≠ NP, not as much. The solver would get at least $1,000,000 either way.