*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.

## No comments:

## Post a Comment

Comments with names are more likely to be published.