Wednesday, August 11, 2010

P != NP

For a simple guy from Madras University, a course on Advanced Data Structures was just too much to handle. After couple of weeks into the quarter, a few of us developed severe stomach upset and sudden affinity towards our IIT classmates. Frankly, I could never wrap my head around turing machines and the P/NP problems. I always asked a JEE #29 to tranlate all this into either Thamizh or at least Thamizh Nadu English. Reason for bringing this subject up is that twitter, Facebook and emails are all abuzz over this. Apparently a major breakthrough has been made that I am hoping will cause all students who have been given a 'B' grade in this course to get a better grade :-)

Even now reading the gory details of the problem, its proof and its rebuttal makes my stomach woosy and heart beat really fast. Really - the day before the exam, the stomach-upset thing got so big among us retards that we told and retold the 'N-P Hard" (which is a class of problems) and 'uN-P Soft' (which is a case of exam fear) joke and laughed out silly. We needed the joke because we'd been shitting bricks otherwise. I hope the guys who 'get' this kind of stuff not further the research anymore in the interest of poor students who have to write exams on it in the future.

16 comments:

Maha said...

unfaartunately, the only consequence is that it is going to provide guidance for future research - naan sollale - wikipedia-ve solliyaachu.

sundar said...

not further the research? hehe, a million dollars is on the line for a valid proof to this problem. :)

btw, because of this news I came to know that out of the 7 millennium prize problems in math, 1 has already been solved by a Russian! and he refused the 1 million dollar prize! :O

Sreekrishnan said...

Curious to know what real world problem would this solve?

Natti said...

Why go through all this trouble to prove this I do not know. Give it to a Tamizhan and he will solve it in minutes. The theorem is a conditionally true one.
if {you are talking about yourself} {
P equals NP
} elsif {you are talking in second person} {
#Your P
P equals UN P
#or His P
P equals AVAN P
#or Her P
P equals AVAL P (let us be inclusive)
} elseif { you are talking second persons(everyone else} {
P equals P( as all the other categories are subset of P)
}

I am writing in tcl. If you need C code to understand this we can compile it and send binary as source code is confidential.

(C) Mine and only mine.

Babs said...

Sreekrishnan,

Most important "real life" applications is in the area of cryptography. I believe that many (most? all?) encryption/decryption algorithms rely on the assumption that P != NP. If P = NP, then such cryptographic algorithms (eg, ssh, https) would be crackable.

This paper explorers some of the interesting physical implications if P where to equal NP:
http://www.scottaaronson.com/papers/npcomplete.pdf

Anonymous said...

Babs
I appreciate your technical analysis. But whatever P it stinks.

Sreekrishnan said...

Babs,

" Rely on the assumption that p!=NP "... and its an assumption. So lets say ... P = NP would it increase the chance of cracking a code? Its still 50 50, given that we are assuming it.

May be my arguments are half baked and half informed - but evvalo padichum athukku mela moolai ettala ! So if only 1 person solved it .. then there arent many who can actually use that assumption [assuming he solved it as p=NP] and crack an encryption technology

Catch My point?

Etho - Veeranam lake thanniyala Chennai water problem solve pannadhu is worth ! I think that was a classical unsolvable problem that Puratchi Thalaivi solved.

So was Veerappan ...

Enna Kandravi P yo !

blackaccord said...

ennamo solla vararnu theriyudhu.. aana enna solrar nnu devanukke thelusu...
These P,NP,uNP are all hard shit at some point in time..

Anonymous said...

the tag sums up:
asingambudicha algorithms!

Anupadmaja said...

SreeKrishnan, NP problems, if found a way to solve will path ways for the class of problems that computers today find impossible to solve. This is not wastage kind of research.

And in the simplest terms, research so far has advanced to the state that if P = NP is proven, that would do/be a key break through. But unfortunately someone seems to have attempted to prove that P != NP. Lets see whats in store for the future.

That said, definitely very tough part of algorithms this is.

Kokki Kumarru said...

I still cannont forget the way we all used to whine "Yavan ya intha algebra va lan kandupudikarthu"

Consultant SEO Services said...

It's really problem. VGK Lighting

teja said...

Hello hawkeye!!was reading all your blogs for the past five days!good work!you are a wonderful writer.Why can't you write some books?(I would love to read those).If chetan bhagat's books are a hit in India yours will be super duper hit!!(Just don't forget to mention some prestigious institutions in the middle for purely commercial purposes ;-)Indians will love it)

Anonymous said...

LOL. Funny write up on a topic that keeps a truckload of people including myself busy. If someone proves P=NP, we will see a load of heuristics that resulted in many PhDs & $$$ NSF funds will go waste. I see a conspiracy on current research to preserve those PhDs and heuristic research. Ha! Do we want to know closed form proof of P <>=NP? Does someone need to calculate exact distance to sun with 25th decimal point?

Anonymous said...

well, no post on avani vittam??

navsingh said...

Two days back i saw this video in youtube,good one