Stop Teutsching Me

A blog about Raghav Kulkarni and other interesting subjects.

Saturday, April 01, 2006

The Spaceship Problem

Help!! The UFO has landed again!! Call Spaceship Hotline 91-146-32! Just kidding, happy April Fool's.

Not long ago, I reported on the PIG vs. NPIG problem, the most outstanding problem in all of livestock. A remarkable solution to this problem has been proposed. In fact, I would go so far as to say that it's out of this world. In short,

The PIG puts the NPIG on a spaceship and then hits the green LAUNCH button. Due to physical effects of relativity, The PIG then easily consumes all of the grain in polynomial time by time-dilating the NPIG. The PIG then hits the red STOP button and brings the NPIG to a grinding halt. It is, of course, crucial that the NPIG accelerates at a rate proportional to the appetite of the PIG, up to the critical speed of 88 mph.

Consequently, the PIG-Turing thesis is false.


Blogger Raghav Kulkarni said...

nice try for PIG vs NPIG.
but the proof has a big fat hole.

due to lenght contraction,
the lenght of the input becomes
even smaller. so running time
is no longer polynomial in
the length of the input.


April 01, 2006 9:20 PM  
Blogger Teutsch said...

Feel free to leave the "lenght" on planet Earth.

April 01, 2006 10:02 PM  

Post a Comment

<< Home

Google Web