Tempus Fugit

Wow, it's already been a year since I created this blog. A lot has changed since then - I'm almost done high school and starting university next year (post to come). Surprisingly, I've only managed to write 40 posts during this time, a record I don't think i'll be able to break considering i'll be even more busy next year. I'll still try my best to keep posting stuff frequently though.

Happy April 18th!

Circles?

As I was doing some last minute practice problems before tomorrows CCC I thought of a possible mathematical paradox involving a simple geometric problem with circles. The problem itself is not the interesting part but the thought is:

As everyone knows, a circle is defined as the locus of all points equidistant from a center. Furthermore, a circle has both a diameter(d) and a circumference (c), and the relationship between the two is:

However, one must realize that pi is an irrational number (some of you might know where i'm going with this), which means we can never say with absolute certainty what the value is. Therefore, even if we know the diameter with absolute certainty, we can never know the circumference, and if we know the circumference with absolute certainty, then the diameter is in doubt. Therefore, we can say that one can never know both the diameter and circumference of a circle. Since a circle has to have both a definable diameter and circumference. We run into a mathematical paradox.

Then I began to think, "Ok, so what does this mean? What's the resolution to this paradox" and soon enough I compiled a list of possible outcomes:

1) There are no such things as circles or any other geometric figure that's dependent on pi.

2) String Theory is to blame as higher dimensions account for the uncertainty in circle geometry (ie. 2D Euclidean Geometry is a simplification even in the flattest worlds).

3) Pi is not a constant but somehow we say it is. Kind of like a mathematical illusion.

4) Pi is in fact a rational number.

5) Because Chuck Norris said so ..

Another thing to consider after this realization: Is circle uncertainty the mechanism behind Heisenberg Indeterminacy? If so, how does it effect observation?

... Worth a thought? At least this distracted me for a while so that I don't fall asleep before the competition.

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

Hello World!

An uprising blog shall soon be erected from the ashes like a soaring phoenix. Stay tuned for my ramblings!