A rough perusal of the abstract doesn't raise any red flags, so this may actually be true. Thoughts?

Never before have I been so happy to see an exclamation mark. (I misread it the first time around.)]]>

Although slightly disappointed as well.]]>

I'm not ecstatic because I know i'm not going to understand the proof.

So... if you'd be so kind as to give me a rundown :D

[seriously, i'll try and understand it first then come back and pester people]]]>

I have tried. I have failed.

Can anyone explain in little words, for the benefit of us sensitive humanities students, why this is remarkable?]]>

The P versus NP problem is a major unsolved problem in mathematics that is important in both theoretical computer science and mathematical logic. Informally, it asks whether every decision problem (a mathematics problem with a yes-or-no answer) whose solution can be efficiently checked by a computer can also be efficiently solved by a computer. It is considered by many theoretical computer scientists to be the most important problem in the field

In essence, the question P = NP? asks:

Suppose that "yes"-answers to a "yes"-or-"no"-question can be verified "quickly". Then can the answers themselves also be computed "quickly"?

The theoretical notion of "quick" used here is that of an algorithm that runs in polynomial time, which usually but not always corresponds to an algorithm that is fast in practice. The general class of questions for which some algorithm can provide a yes-or-no answer in polynomial time is called "class P" or just "P".

For some questions, there is no known way to find an answer quickly, but if one is provided with information showing that the answer is "yes" (known as a certificate, it may be possible to verify the certificate quickly. The class of yes-or-no questions for which a certificate can be verified in polynomial time is called NP.]]>

I'll have a go. I haven't looked at the purported proof beyond the introduction, so I can't really speak to what the author is doing. The proof may yet turn out to be flawed (i.e. not actually a proof); it was just released today, it's 102 pages, and it hasn't been reviewed by anyone other than the author. (I'm sure there are several people looking over it now, but 102 pages of math takes a lot longer to read than, say, 102 pages of a novel.) That said, the question is why this is remarkable (or at least, would be remarkable if the proof holds up).

The P vs. NP question is easily the most important question in theoretical computer science today, and has been for a couple of decades now. It's one of the most important questions in the whole of mathematics even, as evidenced by its inclusion on the list of Clay Millenium Problems. Solutions to those come with a $1 millon prize, as you may have heard about when the last/only mathematician to solve one of them turned down the prize, so it's not just a nice trophy for someone's mantle. This really just establishes that people who aren't you think this is important, which may or may not be persuasive.

Okay, so, the problem itself. There are a lot of problems that arise naturally that a computer can find solutions to quickly. ('Quickly' has a specific meaning here; it means the program runs in

Maybe we're just not clever enough, though, and there's a fast algorithm for even NP problems. In this case, P=NP. This would be shocking for a lot of reasons, although admittedly the biggest one is, "Well, we've tried for a long time and nothing's worked yet." Most people believe that P!=NP, as it seems to gel with our intuitions about solving the two types of problems, so the purported result wouldn't be surprising in that sense. On the other hand, there are provably quite a few obstacles to finding a proof of P!=NP (these obstacles are rather technical, but they are doozies, really), so if this proof works, it represents a huge advance in the state of the art for dealing with these types of questions. That's why this would be remarkable; if the proof works, it must have a good chunk of genuinely new mathematics that should give us insight into a host of other questions.

tl;dr The P vs. NP problem is a about the very basic question of whether or not solving certain types of problems is

The reason is that modern forms of encryption rely on the idea that the encryption is hard to solve unless you have the encryption key. I.e., it's NP if you're trying to crack it, and therefore hard. If you have the key, it's P, and you're good.

So if P=NP, it could mean that all encrypted systems are a bajillion times more vulnerable to spies/thieves/whatever than was previously considered. That could lead to the collapse of the banking system, to name one of the *less* critical things it might destroy.

I know computer scientists who have P=NP "disaster" plans that rival even the government's best nuclear winter survival plans.

Therefore, P!=NP is very good news. If true.]]>

That's overstating things a little. Factorization (which most modern day encryption is based on) is NP-hard, and so it is correct that if P=NP, there would be some relatively quick (compared to our current algorithm) way to factor numbers. But there are a few reasons that you don't need to stock up on canned food if it's the case.

1. Relatively quick is not the same as absolutely quick. Polynomial time is in theory fast, and it's much faster than exponential time, but in practice if the algorithm is above O(n^3) or O(n^4) (which could easily, easily happen; for example there's a polynomial time algorithm for recognizing prime numbers that is too slow to use in practice), it's not fast enough to be useful for factoring.

2. There are encryption schemes not based on factorization; they are well-known and well-studied, just rarely implemented because the factorization stuff is easier/faster for now. People would switch if the factorization stuff wasn't good enough.

3. And anyways, we know for a fact that a quantum computer can factor numbers in polynomial time regardless of the outcome of the P vs. NP problem. So if your friends are worried about P=NP for that reason, they should be even more worried about the possibility of a working, nontrivial quantum computer being built. This problem has led to the development of quantum cryptography.

I think P=NP would be bad because it would mean that we really have no idea what makes a problem hard. At all. That's not as sexy as saying "OH NOES TEH HAX" to some people, but hey, I like this stuff because it's about the limits of human knowledge, not because it lets me shop on Amazon.

Edit: Of course, I'm just realizing that you could be talking about more general methods of encryption than those based on factorization. Yes, I think those will be affected too, but similar caveats apply. Polynomial time is theoretically fast, but in practice, things that run in polynomial time can still be too slow to compute.]]>

http://motls.blogspot.com/2010/08/hp-labs-researcher-p-is-not-np.html

two possible mistakes are given at the bottom.]]>

Yes quantum computers could, theoretically, in the future, crack encryption. I'd point out that the largest number we have yet to factor via that method is 15, and that was incredibly difficult. And larger scale systems are turning out to be much, much harder. And would be very expensive for a long time. And every quantum computer would constantly be in use for academic purposes for a very long time. Etc. This would give us plenty of time to prepare.

P=NP, on the other hand, would allow reductions from anything in NP to something in P. This knowledge could be trivially spread. Some idiot fourteen year old in Romania could easily get his hands on it and decide to start emptying bank accounts.

The argument "polynomial time can be slow" has been empirically observed to be pretty much completely false. Once it's in P, we can do it quickly. Almost universally. While this might be an impediment, it probably wouldn't be.

Quantum cryptography requires an entire new infrastructure. I wouldn't depend on that too hard. And yes, there are other techniques that are not in NP to crack. They are also not widely implemented, and would take time to be installed in critical systems.

And I don't really understand what you mean when you say that P=NP would mean "we really have no idea what makes a problem hard" for two reasons. What makes a problem hard is the amount of time it takes to solve the problem, relative to the size of the input. That's how we define it in computer science. Also, P and NP are hardly the only complexity classes. Check out the Complexity Zoo to see how many people talk about. BPP is an important one. Or, for example PSPACE. It wouldn't really be much of a hit to what we know. It would mostly be a hit to our egos, for not finding the reduction sooner. Oh, and also banking and such.]]>

My mind didn't go to the doomsday scenarios--a sign of my lack of computer science education (the cryptography issue makes perfect sense, I simply hadn't thought about it.) Instead, I wondered what benefits we might get out of this, and realized that (again, lack of CS familiarity) I frankly had no idea how P=NP could help us, but I was sure that it had to have practical, beneficial applications. What might those be? Am I wrong?]]>

Ah yeah, factorization is weirdly placed (or not placed, I guess) in the hierarchy of complexity classes. I always forget that. Thanks for the clarification. And I specifically mentioned "nontrivial" quantum computers because yes, I know that what we have currently is only capable of factoring 15. I wasn't really making any sort of argument regarding the feasibility of quantum computing or cryptography, just that if you're worried about P=NP destroying our banking infrastructure you might as well be worried about quantum computing. Which is to say that I'm not particularly worried about either possibility, honestly.

And really, polynomial time

Finally, I agree, run-time is how we determine how hard a problem is now. But if P=NP, then the traveling salesman problem is in that sense as hard as sorting a list of values. Does that seem right to you? It doesn't to me; one is clearly harder than the other. But if P=NP, then my (and most people's) intuition about what problems are hard is either totally wrong (i.e. the two are as hard as each other, and we were completely wrong about it this whole time) or based on something other than run-time (which would be interesting, but would also mean we're looking at the "wrong" thing this whole time). Either way, we would have been doing something wrong when talking about how hard a problem is this whole time. That's what I meant when I said it would mean we have no idea what makes a problem hard. I hope that makes sense.]]>

I won't argue that polynomial time can't be slow, but the majority of the time it isn't and when it is it usually gets reduced eventually, so I don't find it to be a likely issue.

I see where you're coming from regarding intuition about hardness, but I don't think that breaks down quite so much. I doubt traveling salesman will ever be reduced to O(n log(n)); the intuitive hierarchy of hardness would remain, just without that dividing line. Plus, there are plenty of classes larger than NP.

Edited for grammar.]]>

Traveling salesman is NP-Hard and so P=NP doesn't affect it.

None of this really matters, if P=NP it doesn't mean we're suddenly going to find a series of algorithms to calculate the NP problems in deterministically (I guess this reiterates what I said previously)]]>