P=NP has an infinite number of possible outcomes

Russell Impagliazzo is one of the most original thinkers in complexity theory, and is famous for many wonderful things. One of his papers is on many worlds. The worlds are: Algorithmica, Heuristica, Pessiland, Minicrypt, and Cryptomania. See his paper for the definitions and see this for a recent conference on this topics.

Today I want to talk about a different take on P=NP and possible worlds that we live in. I think that the situation is much more complex than Russell’s view. As usual, I have a different view of things, which I hope you will find interesting.

Some of you may have been at Russell’s invited talk at STOC 2006. It was a great talk, as all his presentations are. But, the coolest part–for me–was that he arrived to the conference with transparencies, overheads. The room for the invited talk was very wide and not very deep. So it was critical that his slides appear on two projectors, otherwise part of the audience would be unable to see his slides.

Of course if he had used Powerpoint this would have been automatic. Since Russell arrived with plastic slides to the conference at the last minute there was a slightly-panicked run to Kinko’s. There they made identical copies of his colorful slides. Later, as he spoke and turned his slides the slides on the other projector also flipped–magically. Of course someone had the job of trying to keep this all in synch. It was a great talk, in any event.

Now let’s turn first to another famous open problem the Riemann Hypothesis.

Riemann Hypothesis

The prime number theorem states that , the number of primes less than , is well approximated by the logarithmic integral:

where

and is the error term.

The Riemann Hypothesis (RH) implies that the error term, , is order –ignoring logarithmic terms. But, the RH is “binary” in the sense that even one zero that is not on the critical line destroys this bound. More precisely, if there is a zero at with , then the error term in the prime number theorem is at least –again ignoring some logarithmic factors. I thank Andy Odlyzko for pointing out this tight relationship between a non-critical zero and the error term.

This is a relatively simple behavior, one bad apple and the whole distribution of the prime numbers changes. Famously, Enrico Bombieri has said that “The failure of the Riemann hypothesis would create havoc in the distribution of prime numbers.”

P=NP is Different

I claim that our problem P=NP is different than the RH, since there is no “one bad apple” behavior. Consider first what a proof that P=NP could look like.

There might be an algorithm for SAT that runs in a reasonable time bound. This would be an immense result, and would change the world. Crypto-systems would all be destroyed, whole parts of theory would have to radically change. This is why many people believe that P=NP is impossible–at least that’s my impression–they say it would be too good to be true. I agree that it would be an amazing situation, but it is only one of a multitude of possibilities.

There might be an algorithm for SAT that is polynomial but with a very high exponent, for example, . This would win the million Clay dollars, but would have a more philosophical impact. Crypto-researchers would worry that eventually the algorithm could be made practical, but it would not have any immediate practical impact. Research papers would have to do a song and dance: “we study an approximation to the following NP-hard problem, that is in P of course thanks to the famous result of X, but we feel our results are still interesting because ”

There might be an algorithm that is polynomial in a very weak sense. What if its running time is

That would be great, I think you still get the money, but crypto people could still sleep at night, without any sleep aids.

There might exist an algorithm that runs in time for some constant that is not even known. Results like this are quite possible, if the proof of the algorithm’s correctness used some indirect argument. Again you still get the cash–I believe.

---

Now consider what a proof that P is not equal to NP could look like.

SAT might require exponential time. The best algorithm might run in time , for example. This type of behavior is what many believe. There even is a “formal” conjecture that the best algorithm for 3-SAT will have this type of running time. Note, even here one needs to be careful: what if the running time is ? Recall Alan Perlis said:

For every polynomial algorithm you have, I have an exponential algorithm that I would rather run.

SAT might have wild complexity. Perhaps for some lengths the best running is exponential, but infinitely often the best time is polynomial in . This could happen.

SAT might be barely super polynomial: what if the lower bound is

Does this really mean anything? Yet it would technically resolve the P=NP question, would be an immense achievement, would win the Clay Prize, and probably many other prizes too. But does it really imply that SAT is “intractable?”

SAT might have no polynomial time algorithm, but there could be random algorithms

The Riemann Hypothesis Again

You might be thinking what if the RH is true, could it have the same complex behavior that P=NP can? In particular, could the RH be true, but with a crazy error term:

Isn’t this the same issue that I raised above? The answer is that this cannot happen for the RH: The following is a theorem:

Theorem: If RH, then for all ,

This is due to Lowell Schoenfeld, who actually proved that RH is equivalent to his inequality.

Is P=NP Ill Posed?

I love the P=NP question, but it occurs to me that in a sense the question is “ill posed.” David Hilbert said once:

“If I were to awaken after having slept for a thousand years, my first question would be: Has the Riemann hypothesis been proven?”

After sleeping for a thousand years knowing if P has been proved to be not equal to NP, would not be nearly as meaningful as knowing that RH has been proved.

To make my point consider three players: Paula, Ted, and George. Paula is a practical minded computer scientist, Ted is a theory minded computer scientist, and George is the best gossip in the department.

There are two scenes. In the first P=NP and in the second PNP.

---

George barges into Paula’s office without knocking. She is about to complain that she is in a meeting with Ted, when George says, “Ted did you hear that P=NP has been proved! I just got off the phone with Lance and the proof is correct.”

Paula sees Ted jump up at this and he says, “are you kidding?” George is out of breathe, but smiling. It’s no joke. “Unbelievable, unbelievable”, is all that Ted can manage.

Paula has never seen George this excited, “no it’s really true. The FOCS program committee accepted the paper, even though she did not submit it. I guess that’s a first, she just missed the deadline or something.”

Paula sits behind a large desk that is covered in books on circuit design and VLSI, says “this is great. Finally, you theory guys have done something that I can use. I can’t wait to get my team implementing the algorithm.” She sees Ted sit down, he is turning pale and mutters to himself, “Dammit, this wipes out Fred’s thesis. I told that idiot to finish it last spring.”

Paula ignores him, “this will change VLSI design and testing and–”

George interrupts her, “well not quite Paula. I hear that the running time of her algorithm is bad.”

“What? How bad is bad?”

“I think its running time is , although I forget if there is a logarithmic factor too. But, P=NP!”’

---

George barges into Paula’s office without knocking. She is about to complain that she is in a meeting with Ted, when George says, “Ted did you hear that PNP has been proved! I just got off the phone with Lance and the proof is correct.”

Paula sees Ted jump up at this and he says, “are you kidding?” George is out of breathe, but smiling. It’s no joke. “Unbelievable, unbelievable”, is all that Ted can manage.

Paula has never seen George this excited, “no it’s really true. The STOC program committee accepted the paper, even though she did not submit it. I guess that’s a first, she just missed the deadline or something.”

Paula who is listening from behind a large desk that is covered in books on circuit design and VLSI, idly checks her Seiko. It’s almost twenty to 12, she needs to leave for her lunch meeting soon.

Ted says, “I knew it, that crazy blogger–what’s his name?–always talking about P could equal NP. Well he was wrong. What an idiot.”

George says, “yeah.”

“So how does the proof go?”

“It’s a circuit lower bound, she proves SAT requires at least size circuits. Avoids the usual roadblocks by using that new combinatorial lemma of Terry. Isn’t this wonderful.”

Paula who a moment ago was hardly listening says, “Did I hear you right? That’s not a very big bound. Let’s see if is a million, let me see, that’s not even a quadratic lower bound. Were those log’s base two?”

“Of course they’re base two, log’s are always base two. But it’s a super polynomial lower bound, PNP!”

---

My apologies to all fiction writers that have ever lived.

Open Problems

My point is simple: There is a huge variance in the potential answers to the question: Does P equal NP?

It’s not simple. Equal, not equal, Equal, not equal. There are an infinite number of possibilities. I think that this is what makes me think that we need to work hard on this problem.

A class of open problems is to prove something like Schoenfeld’s theorem for P=NP. Can we show that some of the above pathological behaviors cannot occur? Or can we show that one pathological behavior implies another? Or precludes another?