Creative Cogitation

So I admit it. I am a geek.  The beauty of the num­bers has long fas­ci­nated me.   It is one of the rea­sons I wound up get­ting an advanced degree in physics.  I con­sid­ered engi­neer­ing,  math­e­mat­ics, and even art as my col­lege major, but physics won out on the fun fac­tor.  Engi­neer­ing was too pedes­trian, Art too risky, and the math­e­mati­cians I saw really didn’t look like they were hav­ing a good time.  I wound up get­ting a mas­ters degree in nuclear physics. but I am not doing any­thing with it these days.  If I can say one thing about get­ting a mas­ters degree (which prob­a­bly applies to any mas­ters degree, not just physics) is that grad­u­ate school taught me to think, to use the tools my under­grad­u­ate degree gave me.  Physics taught me to look at the big pic­ture as many solu­tions to Physics prob­lems apply to a great many very dif­fer­ent types of problems.

But I digress, I really still am a beauty of the num­bers gal.

So one prob­lem, which is kind of like the prob­lem of all prob­lems, is the P verses NP prob­lem.  What is P verses NP? In a nut­shell, the big ques­tion is whether P = NP or P ≠NP;  if P = NP then every prob­lem has a effi­cient solu­tion and we can find it effi­ciently. One might pos­tu­late all prob­lems are solv­able in an infi­nite amount of time, but what good is that?  Only God, per­haps, has an infi­nite amount of time to solve prob­lems; in the real world prob­lems need to be solved in a finite and rea­son­able amount of time. The amount of time is the crux of P verses NP. Are prob­lems really as com­plex as they appear? Is the only solu­tion brute force over an infi­nite amount of time?

By way of exam­ple, con­sider we have a large num­ber of wed­ding guests we need to seat at tables at the recep­tion.  We might want to pair them up into groups of two peo­ple who like each other, so that no one is lonely.  In 1965 a guy named Jack Edmonds devel­oped an effi­cient algo­rithm to solve this par­tic­u­lar prob­lem, and hav­ing an effi­cient algo­rithm means, among other things, you can feed it to a com­puter and solve the prob­lem in a rea­son­able amount of time. Jack Edmonds pio­neered the lingo for P verses NP.  Prob­lems with effi­cient solu­tions are the “P”, in P verses NP.  This par­tic­u­lar prob­lem is called the “match­ing problem.”

But there are many other ways to seat our large num­ber of wed­ding guests that are by far more dif­fi­cult to solve.  Sup­pose we want to make groups of three wed­ding guests who like each other, OR large groups of wed­ding guests who like each other, OR we want to seat guests around a round table such that guests, who can’t stand each other, are not seated next to each other, OR group  three cou­ples at the wed­ding with other cou­ples in a mutu­ally agree­able tri­ads, OR the evil con­verse social sci­ence exper­i­ment where only guests who can’t stand each other are grouped together in one way or another (hey, maybe the wed­ding plan­ner has a thing for the groom).  All the prob­lems that have effi­cient, ver­i­fi­able solu­tions are “NP”.

So if P = NP then every prob­lem has an effi­ciently ver­i­fi­able solu­tion AND we can find it effi­ciently.  On the tech­ni­cal side, even if this state­ment is true, we still may not have the algo­rithm to effi­ciently solve a given prob­lem. The P verses NP prob­lem is an abstrac­tion, there­fore just because we may do some­thing doesn’t nec­es­sary mean that we can…

Nat­u­rally this ques­tion has ram­i­fi­ca­tions well beyond com­put­ing algo­rithms, such as math­e­mat­i­cal proofs, encryp­tion, DNA sequenc­ing etc.

Why think about it at all?  The P verses NP prob­lem is one of the seven Clay Math­e­mat­ics Insti­tute Mil­len­nium Prize prob­lems; solv­ing it is worth $1,000,000.  Not a bad chunk of change, but also real­ize prov­ing P = NP  might solve other Mil­len­nium Prize prob­lems as well, each worth $1,000,000.  How­ever you should know that many the­o­rists believe P ≠NP. Don’t get your hopes up.