P vs NP
Of all the seven millennium prize problems, this problem is the most recently conceptualised and perhaps the most easy to understand and explain.
Loosely speaking, it asks the question:
If the solution to a problem can be checked quickly, can the solution also be obtained quickly?
Take the Rubik's cube, which, if you were given a solved version, would definitely be easy to verify. However, can it be easily solved? Turns out, it can. The term "quickly" or "easily" here means that the number of steps can be expressed in polynomial time, as opposed to exponential time.
Viewing from this perspective, Polynomial Time (known as class P) is sure as hell a lot quicker than Exponential Time. P is the simplest, most fundamental complexity class.
There are 43 quintillion permutations of a 3 x 3 Rubik's cube. If a person had as many standard sized cubes as permutations, the setup would cover the Earth's surface 275 times. But even this amount is not large enough for algorithms. Computers follow repeated instructions really well, and quickly. The algorithms can quickly find the permutation out of the 43 quintillion, and produce a solution (within 20 rotations, because #20isgodsnumber) that can solve the cube. The number of steps in this algorithm can be expressed in polynomial time. This means that the solution is also quickly attainable, even if it may not be true for some humans. This puts Rubik's cubes into the class of P.
Another complexity class, called NP, stands for Non-Deterministic Polynomial Time, houses those problems which are quickly checkable, but it wasn't easy getting the answer. An example is Sudoku. An ordinary game can usually be solved by the computer within seconds, but once the size of the board is scaled up, it takes much longer.
Don't get me wrong, it generally takes longer to solve a 4 x 4 Rubik's cube than a 3 x 3, but the amount of time increment isn't the same. Solutions of the Rubik's cube follow a certain Polynomial Time. Solutions to Sudoku follow an Exponential Time.
You can see that the graphs are comparable initially but they diverge drastically after awhile, and the exponential graph increases faster than the polynomial graph. This means that scaling up a Rubik's cube problem still confines it within our algorithm's abilities, but scaling up a Sudoku problem would require a time beyond what we can handle.
The number of steps to solve a Sudoku problem increases exponentially when we increase the grid size. This essentially makes Sudoku an NP problem.
Factoring a number may seem easy.
But it faces the same problems. As we make the numbers larger, it also becomes a lot harder to find its' factors. It took several machines 2 years to factor a 232 digit number. This means factoring is also an NP problem.
The terminology of all these complexity classes may seem confusing and arbitrary, but they're all part of a bigger complexity zoo. Beyond the P and NP classes lie the special fundamental cases known as NP Complete, and problems that are at least as hard as NP Complete, known as NP Hard.
Beyond these, there exists classes of problems where even the checking the solution is hard, like, given a point of time in a particular chess game, what is the best move at that instant? How do we even go about checking that? This class is known as EXP, or Exponential Time, where even checking the solutions take exponential time.
Caught in between subsets and intersects, there exists other classes like PSPACE, Polynomial Space, where time isn't an issue, but it takes exponential memory to compute a solution. Tic Tac Toe falls into this category. Also, because of the nature of problems today, the class of Co-NP describes problems where it is easy to exclude the incorrect solutions, instead of checking for the correct ones.
Interesting fact: Proving things is a Co-NP Complete problem. The P vs NP problem is hence a Co-NP Complete problem. That's why it's been so hard to prove things.
The class of BPP, Bounded Error Probabilistic Polynomial Time, describes the problems where the problem is quickly solvable, with an error probability bounded away from 1/3 of all instances.
When quantum computing is involved, this class is called BQP, Bounded Error Quantum Polynomial Time.
As of today, Wikipedia documents a total of 66 complexity classes, too many to fit neatly into a Venn diagram.
One million dollars, in USD. (Most sources tend to leave out the currency) That's the amount that will be awarded if anyone solves the P vs NP problem. A proof either way will have severe implications in the whole world. Or maybe someone will find a way to prove that this problem cannot be proved, which happens sometimes.
#20isgodsnumber - 20 is known as God's Number because any permutation of the 3 x 3 Rubik's cube can be solved within 20 rotations (inclusive of quarter-turns and half-turns).
