Stop Teutsching Me

A blog about Raghav Kulkarni and other interesting subjects.

Sunday, March 12, 2006

The PIG vs. NPIG problem

One of the most important open question in livestock today is the notorious PIG vs. NPIG problem. The problem is to resolve the equality PIG = NPIG. How to resolve this equality?

As in my previous Raghav = co-Raghav post, it is clearly appropriate to ask the question, "How fat is she?" Since that last post, I have received a flurry of emails requesting that I comment on possible answers to this question. I regret that I do not have time to respond personally to each of these messages. However, if there is verified significant progress towards an answer, you will hear about it first on this weblog. Moron that later.

For now we shall restrict ourselves to the case where the pig is polynomial-time computable. This means that we don't have to wait too long for the pig to "finish." No, the pig is not Finish. Therefore, the npig is not Finish. In particular, the npig is not Polynomial-Time Computable. It follows immediately that PIG ≠ NPIG.


Post a Comment

<< Home

Google Web