Should we spend money on p=np

Dick Karp started all of this. He is, of course, a Turing award winner for this famous work on the P=NP question. He has also won just about every award possible: he recently (2008) was one of the laureates awarded the prestigious Kyoto Prize by the Inamori Foundation.

While Cook proved the first basic theorem about SAT, I believe that one could argue that Dick’s work was essential to get the “balling rolling”. His contribution was in setting up the problem in a clean way, in naming it in a beautiful way, and in showing that it had applications well beyond logic and complexity theory. However, do not get me wrong, Cook contribution was immensely important. In a later post I would like to go over how the community initially reacted to Cook’s and Karp’s work back in the early 1970′s.

Today I would like to suggest that the government (NSF?) should fund a major project on P=NP, with the goal of accelerating the discovery of a solution. The reason I mention Dick is that he and I do not agree on this issue. I have had many conversations over the years with him on this topic: should we fund research expressly to attempt to solve P=NP? I believe that we should. Dick does not.

I am curious what you may think, so please let me know. I do not want to give our views now. I would prefer to hear your thoughts first: so please post a comment or send me an email. Given the huge amounts of money being spend by Washington these days, how could a few tens of millions of dollars not be a good investment to get people to work hard on this problem?

1. February 23, 2009 5:27 am

First of all, thanks for a very entertaining blog! I learned a lot about TCS in previous decades and your view is always interesting. There are also a lot of interesting problems.

Regarding your question, I generally disagree with you. The main reason is that, although P=NP is a very important problem, I don’t think it’s the most important thing. Obviously, there are many more important things that we still can’t put enough money on; things that could save thousand of lives, things that could create new business, and so on.
Besides, I still doubt if there’s going to be a huge impact (outside our community) once the problem is solved.

Best.

February 23, 2009 1:09 pm

There are many important problems in science and mathematics, of course. But the key is that P=NP would have tremendous implications beyond just theory. I post more details on this later on. Thanks for your comment.

2. February 23, 2009 6:01 am

I originally came by to apologize for the inclusion of one of my non-related blog posts in your automatically generated list above, even though it’s wordpress’s fault!

But then here is the the most important problem in the computer field being tackled by a follow blogger! Hmmmm, maybe this crazy automatic link thing has some merits!

I applaud you for this and even though I’m not in the biz, I understand the scope of this vexing problem. I wish you much luck and hope you have fun storming the computational complexity theory castle! To the battlements with you!

So what will ya do with the cool mill if ya win it?

The scientifically impossible I do right away
The spiritually miraculous takes a bit longer

February 23, 2009 1:18 pm

I like your question: “So what will ya do with the cool mill if ya win it?”

First, my goal is to get the community to work on the problem. I would probably be the least likely person to solve it. I do think that not enough people are working on the problem.

My post on the solution to another famous problem, the LBA question, shows that sometimes there are surprising solutions to long open questions.

Back to your question. Given the way the economy is going I might use the “cool mil” either to pay bills or perhaps if we hit enough inflation to get a cup of coffee at Starbucks.

3. February 23, 2009 2:28 pm

“There are many important problems in science and mathematics, of course. But the key is that P=NP would have tremendous implications beyond just theory. I post more details on this later on.”

I will be waiting for this post. I believe there are many people, like me, who don’t understand the implication of P=NP problem (especially if P=NP).

“First, my goal is to get the community to work on the problem.”

I don’t understand this. Isn’t the community working hard on this problem? My thought was that, although few people are working directly on the P=NP problem, there are so many complexity theorists who work really hard on related topics like hardness of approximation and random extractor. Wouldn’t this lead to solving P=NP in the future?

I also would like to know your opinion about the following comment by Leonard Adleman. On the blog “The A in RSA” linked from this blog, he answered a question why he is not working on P=NP as follows.

“I don’t work on it for 2 reasons. First, I did work on it for a few years as a youth, I had a few ideas worth (I thought) writing down (see “Time Space and Randomness” by moi), but ultimately I came to the conclusion that the problem was not “ripe” – ready to be solved. A few more decades (at least) of research would be required …”

My question is, if the problem is not ripe then is it possible to provide a huge amount of money so that we can solve it before its natural due date?

February 23, 2009 11:43 pm

Of course its hard to say when a problem is “ripe” for solution. A good example, I believe, is the famous list of 23 problems listed by Hilbert at the International Congress of Mathematicians in 1900. Hilbert was convinced that that his seventh problem (on when $a^b$ is transcendental was hard. He thought that it would be very long before it was solved. It was completely solved just three decades later. Several other problems that he thought might be easy are either open or took much longer to solve.

My point is simply that we should expect surprises. But one thing is certain, if no one seriously works on a problem it is unlikely to get solved.

4. February 23, 2009 4:52 pm

Type: especially if P=NP –> especially if P!=NP

5. February 28, 2009 6:27 pm

I tend to believe that P != NP … In natural mechanics, as anything neural becomes more complex, the logical distance from the child endpoint always increases exponentially in direct proportion to the amount of decisions introduced.

So, take the example of a tree branch, and let a single branch with one leaf be our simplest example of one. Also take an ant, who starts on any leaf of this branch and has to find his way back to that branch’s trunk. For the purposes of discussion, the ant requires no thought to walk forward, he always knows he’s doing that.

In the simplest example, the ant makes no decisions, and walks forward towards the trunk, reaching it without any ‘thought.

However, if a second, ‘child’ branch grows out of the simple branch and has its own leaf, the logical distance an ant would have to travel from that second branch grows in exponential proportions to the amount of decisions the ant has to make at that intersection. Could the trunk be along the second branch, or should the ant keep moving forward? Lets say the ant chooses the second branch, realizes his mistake, and turns around. If the ant has no memory, it could even move back to the branch it was on originally and stay in this cycle.

Now, what if a third branch grows right out of that intersection, or out of the second branch? The problem becomes more complex in direct relation to the number of possible paths. To make its little ant life even worse, if a branch decides to grow out of a branch intersection, it needs to choose between THREE branches, exponentiating the complexity.

The likely solution is more like (P = X root of NP) though we lack computational hardware powerful enough to prove this yet.

Since the P=NP problem traditionally deals in YES/NO decisions, we can assume that the solution to this problem is more like P = sq. root of NP.

March 2, 2009 9:06 am

Not sure what you mean here. I think your intuition about complexity is right, but making that precise is the key issue.

6. February 28, 2009 6:35 pm

“I will be waiting for this post. I believe there are many people, like me, who don’t understand the implication of P=NP problem (especially if P=NP).”

Imagine that the questions to answers we already know could become as easy as solving them would have been, had we only known the right question to ask. As a more practical example, imagine being able to ‘prove’ that every problem you solve was solved ‘correctly.’

This is largely considered to be the absolute most important problem in computational theory and analysis. Its also the nightmare of people who make their money in quality assurance.