re: The Humbling Power of P v NP

Some engineer out there has solved P=NP and it's locked up in an electric eggbeater calibration routine. For every 0x5f375a86 we learn about, there are thousands we never see.

In “The Humbling Power of P v NP“, Lance Fortnow urges theorists to try and solve P v NP “not because you will succeed but because you will fail” . This is the Kobayashi Maru character test for theorists it seems.

So what about non-theorists?

My answer is: So what if a problem is NP-complete? Does this mean that we are going to use that fact as an excuse to not solve it, or present a lousy hack as a solution? Or do people think that such problems do not come along the way of “a real professional”? They do, but theorists are trained to recognize them when they see them.

Just like theorists then, “practical computer people” must try to solve (using whatever tool they see fit) an NP-complete problem (like the TSP for example). Not because they will solve it optimally, but because there will always be a better solution. And by seeking it and understanding that “computation is a nasty beast” they will become better programmers professionals.

Update: You should also read:

One thought on “re: The Humbling Power of P v NP

  1. You cannot throw money at such a problem, more CPUS more storage and such stuff will not work.

    You must use your gray cells…

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s