P = NP?

People have been sending me this paper that “proves” that P != NP. These sorts of papers make the rounds regularly, and my advice is to not pay attention to any of them. G.J. Woeginger keeps a list of these papers—he has 43 so far—and points out:

The following paragraphs list many papers that try to contribute to the P-versus-NP question. Among all these papers, there is only a single paper that has appeared in a peer-reviewed journal, that has thoroughly been verified by the experts in the area, and whose correctness is accepted by the general research community: The paper by Mihalis Yannakakis. (And this paper does not settle the P-versus-NP question, but “just” shows that a certain approach to settling this question will never work out.)

Of course, there’s a million-dollar prize for resolving the question—so expect the flawed proofs to continue.

Tags: ,

Posted on November 4, 2008 at 12:12 PM • 27 Comments

Comments

Daniel • November 4, 2008 12:40 PM

And how many papers there are “proving” the security of their crypto through reducing the underlying problem to something NP-complete! Even if NP-complete problems turn out to be strictly super-polinomial, it has no bearing whatsoever on security: complexity is concerned with worst-case behavior, whereas security depends on average and best-case behavior.
It is actually depressing that so many people misunderstand complexity theory and its uses.

Daniel • November 4, 2008 12:43 PM

I mean polinomial reduction of the solution of some NP-complete problem to cracking their crypto, which proves that cracking their crypto would solve an NP-complete problem.

Jib • November 4, 2008 2:39 PM

I don’t get it.

P=NP when N==1, and P!=NP when N!=1.

So, my solution to P vs. NP: It depends?

Seth Breidbart • November 4, 2008 3:25 PM

Daniel, that’s backwards. You show a problem is hard by reducing an NP-complete (or NP-hard) problem to yours, not the other way around.

Jurjen • November 4, 2008 5:41 PM

Original observation by Peter van den Emde Boas:
AI people assume P==NP, so they can solve their hard problems.
Crypto people assume P!=NP, so their systems stay secure.
We’ll see who is right, eventually.

RH • November 4, 2008 6:18 PM

@Seth: I think what he’s saying is that NP-completness does not mean cryptographic security.

As an example, I could have a system which can be cracked in O(n) for 99.99% of the cases, O(exp(n)) for the remaining 0.01%, and still call the cracking problem NP-complete. In that example, despite being NP-complete, the cracking problem is most often trivial, with a scant few cases that are nasty.

I think the NP-completeness reduction is not meant to show that a system is secure, but rather to show that it is not insecure. Any system which is not NP is going to have a polynomial time crack, guaranteed. A NP system may have one too, but its no longer a guarantee built into the mathematics

Peter • November 4, 2008 7:06 PM

“These sorts of papers make the rounds regularly, and my advice is to not pay attention to any of them”

I would tend to agree with one caveat, that being unless there is a very convincing general argument presented then there is little point in reading the paper.

These types of problem are generally highly intractible and the solution of which are often extremely involved and convoluted – the proof of Fermat’s last theorem being a prime example. More importantly, to formally verify a proof of a problem of the difficulty of “P = NP” would likely involve years of work in itself.

Personally, I would deride the idea of putting up such a massive public monetary prize for (dis/)proving what is a set of very involved problems, then effectively asking the rest of the scientific community to act as referee.

some guy • November 4, 2008 7:25 PM

“These sorts of papers make the rounds regularly, and my advice is to not pay attention to any of them.”

Unless it actually solves the problem in which case you’ll* have to pay attention to it. It’s no fun sifting through the muck but someone has to do it.

*I don’t mean you in particular Mr. Reader O’myPost.

Nyhm • November 4, 2008 7:28 PM

Here’s an “in-the-margins” blog comment for the modern age:

“Nyhm’s Last Theorem” … Now where did I save that P = NP proof? Must be on my encrypted drive … kicks the bucket

200 years later, Nyhm’s Last Memory Stick has yet to be decrypted.

fermat • November 4, 2008 10:43 PM

Bruce, i’ve read somewhere that you can reduce any NP hard problem into P with your bare fists. Is that true?

S • November 5, 2008 7:57 AM

As far as peer-review is concerned, don’t portray the “expert community” as a kind of irreproachable assembly. When Wiles proved Fermat’s Last Theorem he knew well enough to work in absolute privacy and not reveal his efforts to anyone. Even when he began to present the proof almost no one knew where his presentation would culminate until the final stroke. The “expert community” is full of dead beats and wackos. Peer review is one thing, but some of these people would easily refuse to examine a valid paper from someone outside the community, only to turn around and appropriate the substance for themselves.
The “expert community” at large is not expected to review Clay submissions. And the simplest way to solve the problem of frivolous sumissions is to charge a fee. The PTO charges fees for applications which in turn are consumed in examination.
I know with absolute certainty, that some of the warnings not to waste your time reviewing these papers are a reflection of territorialism (ie “who the hell do you think you are?”). One clue begins with a consideration of how few experts there are in complexity theory, and how fewer still there are that come here. Why in the world would YOU care whether anyone wasted their time reading this stuff? Indeed, for some it might be just as pedagogical as Garey and Johnson’s Computers and Intractability. Should the student not read this book because they didn’t first receive someone else’s permission?
Besides, the next advance in information security may very well not belong to any complexity class at all.

hieronymous coward • November 5, 2008 8:13 AM

@fermat:

OF COURSE IT’S NOT TRUE – BRUCE USES BRAINS, NOT FISTS!!!

HOWEVER, BRUCE SCHNEIER’S SPINAL CORD REFLEXES CAN REDUCE AN NP-COMPLETE PROBLEM TO AN O(N) ALGORITHM FASTER THAN YOU CAN BLINK!!1!

S • November 5, 2008 8:14 AM

“Who the hell do you think you are?” is EXACTLY why Warren and Marshall endured years of ridicule and contempt from both scientists and the drug companies. These guys from some no place clinic in Australia dared to even try and persuade anyone that stomach ulcers are caused by Helicobacter pylori, and not excess acid from spicy foods or stress. Oh Oh, someone’s toes got stepped on. And in the process years passed before the public benefited from their results.

Incredibly, the same attitude is now deeply seated in the Valley. If you don’t know the right people and don’t get the right “permission” your idea is rejected out of hand. If you think academics is any different you have another thing coming.

Troy • November 5, 2008 8:15 AM

@Nyhm,

The funniest bit is that 200 years after Nyhm’s memory stick IS decrypted and the proof retrieved, the same memory stick is decrypted with a second key which reveals a journal explaining that the memory stick was simply filled with random bits in an attempt to take the credit for the earliest proof of P=NP.

greg • November 5, 2008 9:23 AM

@S

And What is the Signal to Noise ratio? 1000:1, 1000000:1? When the idea is valid, or in math true/correct it will get there. But if i had a buck for every person who gives a quote just like you have and a pile of crap idea to follow I would be a lot richer than I am now.

The News groups get people with P factoring algos that work ever second week and yet never factor any interesting numbers. etc etc

What worse is none of these people seem prepared to actually learn the material. Some even claim that by learning the material (ie what we already know) will some how cloud there brain into the tunnel vision of the rest of whatever conspiracy they subscribe too.

S • November 5, 2008 11:33 AM

@greg

No one asked you to review anything. And how would you know what the noise was UNTIL you tested it. So…you are declaring it’s all crap because you say so? Exactly which papers are you referring to, and to which quote of mine are you referring?

S • November 5, 2008 11:42 AM

@greg

And if fact, if your only motive is money you might consider how much wealthier you would be than that, if you had ever reviewed one single valid paper.

Where would anyone be if all new things were rejected out of hand the way you are, how would anything EVER rise to the top? They wouldn’t. The fact is success doesn’t wait for anyone to give permission. That’s why so few advances come from academia. The level of creativity there is extremely low.

A big clue this is true is the nature of the categorical rejection – ‘we are few in number and don’t really have time to review all this garbage so stop submitting it’ taken in conjucntion with the postulate ‘if there will be anything valid, it will come from us’. So, in other words KEEP OUT.

Don’t tell me this isn’t true. I am in good company.

kangaroo • November 5, 2008 1:40 PM

S: “Who the hell do you think you are?” is EXACTLY why Warren and Marshall endured years of ridicule and contempt from both scientists and the drug companies. These guys from some no place clinic in Australia dared to even try and persuade anyone that stomach ulcers are caused by Helicobacter pylori, and not excess acid from spicy foods or stress. Oh Oh, someone’s toes got stepped on. And in the process years passed before the public benefited from their results.

That’s how science is supposed to work — it’s not a bug but a feature. The old “extra-ordinary claims requires extra-ordinary evidence” — or “the default is the conservative viewpoint”.

No need to bitch about it; otherwise, every crackpot idea would demand equal time. In the long term, the revolutionary good ideas will make it through the scientific review process — even if it take centuries.

Clive Robinson • November 5, 2008 11:38 PM

@ fermat,

“Bruce, i’ve read somewhere that you can reduce any NP hard problem into P with your bare fists. Is that true?”

No, not quite he holds a length of hosepipe gives the “book cover” look and asks nicely…

Mind you speaking of “back door” / shortcut attacks, from an earlier blog, one poster has suggested that the Russian Maffia now use soldering irons. Which of course does involve less effort if the “look” fails.

Clive Robinson • November 6, 2008 12:11 AM

@ s, greg, kangaroo,

The peer review process is not ideal, and worse the fact the reviewers remain anonymous has given rise to alegations of theft etc.

It is out moded and was an invention not of practicioners but publishers and as such is a protection mechanisum.

The problem is that the reputation of the journal is what brings in the money for the publisher. If to much outlier or junk papers get into the journal then sales will (probably) fall. As a publisher is unlikley to have the knowledge or ability to understand the majority of papers submited for publishing, how do they filter out the junk. The answer is of course ask somebody that is an expert, but they in turn don’t want to be accused by some hot head so the (supposed) need for their identity being kept secret.

It is this “protect the publisher” system that gives the conservative result, and also due to secrecy alows the process to be abused.

Unfortunatly the funding model in science post WWII gave real teath to “publish or be damed” attitude which made things worse. However what makes the problem worse still is the modern addition of “the more times the better”, which gives rise to an imense number of marginal improvment papers of little substance.

This overall system does indead enjender a “don’t rock the boat” / “keep of the grass” mentality, which is to sciences detriment.

I do not know what the best solution to the problem is (or if there even is one). But I am sure that it will require a change in the funding model. I also suspect that the Internet and peoples blogs will start the process of breaking down the power of the “publisher” and their protection mechanisum. Hopefully this will give rises to changes in the peer review process which will eleviate a few of it’s acknowledged proplems.

greg • November 6, 2008 6:37 AM

@Clive Robinson

I am working as a scientist and have to publish my work. I know all about publishing papers and review.

First of all its not that anonymous. I always opt for non anonymous when i review papers. 2nd the editor etc do know who reviewed the paper and often you know who did anyway from the writing style.

I can see problems with the review process, but i can’t think of a better way to cut out the quite substantial amount of dross that folk submit to journals (ie the editor clearly did not read them). I think a more open system is perhaps a good idea. But i can also see the point of anonymous reviews. Example that guys paper you are reviewing will be on the funding board with your proposal next month.

However the impact factor game has to go. The top journals like science and nature regularly have the worst articles. They also have the fraudulent ones as well. The bean counters need to get out of the “one metric to rule them all” box. Whats worse is that a company sets the impact factors for journals and is not reviewed or open at all.

My first move is I that I try to publish in open access journals only and then pay for open access otherwise. Personally open access is the start of removing a few publishers.

Next we need a method to cut out dross. There is more published now than ever and its impossible to keep up sometimes. but the real problem is the amount of crap published. Or that is attempted to be published. I often get papers for review that simply are not finished and have not been proof read.

Now move over to the P=NP type papers and the problem with true crack pots and nut cases becomes huge. Its like the patent offices refusing perpetual motion machines without a working prototype. It cuts out dross.

The same with P=NP/prime factorizations. These have applications. Lets see the results. compared to the proof, it should be quite trivial. Extraordinary claims need extraordinary proof.

Greg

greg • November 6, 2008 7:09 AM

@S

“That’s why so few advances come from academia.”

You might want to check your facts on that one. Industry has been good at application and refining. But they sux at discovery. Even the labs that do discovery are almost always combined with a university of some sort with a whole swag of government funding for basic science…

And no I don’t mean blanket dismissal in all cases. But really the number of p time factorization methods that people can come up with and never implement is staggering. In god we trust, the rest of you show me the code/results/data. Its similar with P=NP. Ok so that not the case with P!=NP. But really you can’t be bothered writing up the result properly and yet you did the work?

The easy part is writing up the results properly in a clear and concise manner and is a fundamental part of science. All these type of papers usually share a common theme of sloppy notation and writing.

Oh and yes I get asked to review papers quite often as a matter of fact. I reviewed 3 papers last month.

Dom De Vitto • November 8, 2008 6:00 AM

Are you still allowed to carry these problems on a plane? (in a clear bag, obviously)

Sounds risky, you could easily use them to bore the staff and other passengers to death, take over the plane, fly it into the sun and destroy all life on earth.

Kip, get your notepad… !

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.