A little teaser for a future post ... if you want to know more about this picture, look up the travelling salesman problem. It is incredibly relevant to this Millenial Problem!
Computer science is largely concerned with figuring out how long it will take to run an algorithm; a more time-efficient program is both better for saving time and energy, but is also probably more logically concise.
If you ran an algorithm to find the largest element (n) in a list, the program would (at a minimum) have to consider each item in the list. If you extend this reasoning, it is fairly intuitive that an algorithm’s execution time is directly proportional to the number of elements (N) it is handling. If you wanted to run a more complicated program, it might have to deal with numbers more than once; these algorithms might have running times proportional to N^2, N^200 ....
The “P” in “P = NP” stands for 'polynomial time'. P refers to the set of problems whose solution times are proportional to polynomials involving N's. The "NP" in “P = NP” stands for non-deterministic polynomial time, and is the set of all problems that can be verified in polynomial time. If you want a little elaboration on the 'non-deterministic part', I will probably
Note the difference. Solution time is the execution of a program, such as finding that the largest number in a list. VERIFICATION time is the time that it would take to check that a number would be the largest in that list.
So the problem P=NP is drilled down to this. If I can check that a problem is right in polynomial time, can I solve it in polynomial time? Or, if I can check a solution to a problem easily, can I solve it easily?
While this may not seem like a hugely important problem, to crack it would have some pretty crazy consequences. Essentially, modern cryptography (the thing that keeps all our data safe online) works on the assumption that P does NOT equal NP.
Take public-key encryption. This essentially involves two computers that want to share data generating huge prime numbers, and multiplying them to create a huge-almost-prime number. This is passed over the internet, under the assumption that while it is easy for each person who have the number to check if something they have is a factor of the large number, it is very difficult to find that factor by trial and error.
If it were easy to find that factor... goodbye banks!
It's amazing to think about how the world is, in many ways, balanced on unproven theories of mathematics and physics. It's perhaps even cooler to think of a world in which we had the answers - what more might we be able to do?