Home

re: The Humbling Power of P v NP

2009/10/22

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:

Advertisements

One Response to “re: The Humbling Power of P v NP”

  1. kangelos Says:

    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:

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: