God's Number is 20

As many of my friends know, I am a competitive speedcuber (one can search up my WCA profile).

I love solving puzzles, and more importantly, I love the mathematics behind it. For some time now in the cubing world there has been some progress made into solving an algorithm which produces a solution having the least possible number of moves, the idea being that an omniscient being would know an optimal step from any given configuration. This is known as God's algorithm. The number of moves this algorithm would take in the worst case is called God's Number.

Recently Morley Davidson, John Dethridge (also a TopCoder), Herbert Kociemba, and Tomas Rokicki proved that God's Number for the standard 3x3x3 Rubik's Cube is exactly 20.

Why is this a great leap forward for cubers? Simply put, imagine constructing an algorithm to optimally solve all 43,252,003,274,489,856,000 positions of the cube. Easy, no? It took 3 decades to get to this stage ..

Here's the article for further reading.

P != NP ?

Stumbled upon this interesting article today on the famous P versus NP problem. Thought I should share it with my fellow CS enthusiasts.

For more, please visit here.

(Aug. 9) -- News that Hewlett-Packard employee Vinay Deolalikar may have solved one of computer science's most confounding mathematical problems -- known as P = NP or P versus NP -- is buzzing around the smart side of the Internet. The problem was formulated by Stephen Cook and Leonid Levin in 1971, according to the Clay Mathematics Institute, which has been offering a $1 million prize for its solution. Now, mathematicians are in the process of scrutinizing Deolalikar's proof, released on Friday, which says that P is not in fact equal to NP.

P versus NP
Roughly, the mathematical problem asks if "questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure," according to the Clay Mathematics Institute. In other words, are there really problems whose solutions can be easily verified but not easily solved?

To illustrate the type of problem that could occur if this were true, Clay imagines a college housing scenario wherein 400 students have applied for rooms at a college that can only accommodate 100 of them. A selection of 100 students must be paired together in rooms, but the dean of students has a list of pairings of certain students who cannot room together. The total possible number of pairings is ridiculously large -- more than the total number of atoms in the universe -- but the solutions, i.e. the list of pairings finally provided to the dean, is easy to check for errors: If one of the dean's prohibited pairs is on the list, that's an error.

If P = NP, then problems that appear hard to solve (as the one above) actually have very easy solutions. Deolalikar says he has proven that P does not equal NP -- as many mathematicians have believed -- meaning problems do exist that are easier to solve than to verify.

P
In the equation P = NP, P stands for "polynomial time" and refers to a set of problems whose solutions are easy to find.

NP
NP, meanwhile, stands for "non-deterministic polynomial time" and refers to a set of problems whose solutions are hard to find, but easy to verify.

Algorithm
A set of instructions used to solve a problem. We use them without thinking about it in everyday life, such as when trying to figure out why a lamp doesn't turn on.

N
The number of elements involved in an algorithm. The time it takes to execute many common algorithms is proportional to N or N raised to a power. For example, to determine why a lamp is not working, we might consider three elements:

1. The lamp is not plugged in.
2. The light bulb is burnt out.
3. The lamp is broken.

With only three elements to consider, our algorithm will not take very long to complete. But, if we are trying to determine why our computer won't turn on, we are presented with more elements to consider: Is it plugged in? Is it frozen? Does it need to be rebooted? Does the operating software need to be re-installed? Is it broken? And so on.

Polynomial time
Refers to a "fast" or "efficient" amount of time needed to execute an algorithm, as in N or N raised to a power. Problems classified by "P" in P = NP are those whose solutions can be solved in polynomial time. Problems classified by "NP" can be verified in polynomial time but require exponential time (in other words, far, far more time) to solve.

NP-Complete
The set of NP problems (the majority of NP problems, in fact) that could be solved by adapting a single, easy solution, if an easy solution were possible.

Read more about P = NP on MIT's website.

pnp12pt