Imagine a chessboard. Place two rival queens on it so they cannot attack each other directly. Easy? Now repeat the process with six more queens. Complicated, but possible.
Now extend the problem to boards of any size, with any number of preset queens. The so-called "1000 queens problem" is just an example used to explain a far more complex challenge: "P versus NP". The Clay Mathematics Institute offers one million dollars for the first positive proof of this problem.
The Seven Millennium Problems
There is a very interesting competition called the "Seven Millennium Problems". Launched in 2000 by the Clay Mathematics Institute, it aims to find answers to seven classic problems that have "resisted" a solution over the years. So far, the only problem to receive a proper proof is the "Poincaré Conjecture", developed by Russian mathematician Grigori Perelman.
The institute did not hesitate to offer him a million dollars for his work, but Perelman refused, saying his contribution was no greater than that of mathematician Richard S. Hamilton, who had previously suggested a solution.
Understanding P vs NP
Another of the great problems the institute wants to see solved is the famous "P versus NP". To try to understand it, the most common approach is to turn to chess:
Didn't help? Don't worry, it didn't help me much at first. P versus NP is more complicated than tossing a couple of queens on a board, and its reputation for being impossible is well deserved. In very relaxed terms (and I say "relaxed" with all sincerity) we can say that problems called P are easy to solve and verify with algorithms, within "polynomial time".
On the other hand, NP problems are easy to verify if a solution is correct or not, while reaching it demands a lot of time and effort, with notable losses in efficiency. Robust examples of NP problems are puzzles, Sudoku, and even Minesweeper.
Now, what would happen if you find the key to solving an NP problem in polynomial time, with great efficiency? If you accomplish that, you will prove that there are no differences between N and NP (N = NP), causing the Clay Institute (and not the University of St. Andrews, as has been repeated ad nauseam) to throw a million dollars in your direction, followed probably by a Nobel Prize, and the hatred of cryptography experts around the world.
Most experts lean towards N ≠ NP, and honestly many things depend on it (the previously mentioned encryption being one). But if you're going to try anyway... good luck. You'll need it.
