Forty Years of P=NP?

An anonymous reader writes "In the afternoon of May 4, 1971, at the Stouffer's Somerset Inn in Shaker Heights, Ohio, Steve Cook presented his STOC paper proving that Satisfiability is NP-complete and Tautology is NP-hard. 'The theorems suggest that Tautology is a good candidate for an interesting set not in [P] and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory.' And thus Cook formulated what was soon to be called the P versus NP problem. The rest is history. Here's the 1971 STOC Program (there were 143 attendees) and what that sacred ground looks like today."

Comments

P=NP is a waste of time.

[Anonymous Coward]

The only way to know if you can solve a problem as fast as you can *know if it can be solved or not* is to solve the fucking problem.

Amateurs.

Re:P=NP is a waste of time.

[Anonymous Coward]

No shit. Just like the only way to solve the P=FP problem is to post a first post.

Re:P=NP is a waste of time.

[martas]

Wow, that's a level of stupid I haven't even seen on 4chan in a while...

Re:P=NP is a waste of time.

[mark-t]

Actually, that's not true... It can take far less time to construct a method for solving a problem than it can to actually solve it, and analysis of the method constructed can readily reveal the time that the method actually takes to utilize, again in far less time than it actually takes to solve the problem at hand.

Actual origins are even earlier

[Anonymous Coward]

Alan Cobham wrote a paper defining the complexity classes L and L+. These are exactly P and NP. He may also have originated the concept of defining the complexity of an algorithm as a function of the input size.

Alan did not however show that there were a large number of problems which were in reducible to L+

P=PN

[jjohn]

15 years of developing software and I still don't know what P vs. NP means.

Sad, sad old hacker.

Re:P=PN

[war4peace]

Make that two of us. And guess what, I don't even care :)

Re:P=PN

[betterunixthanunix]

Perhaps you should read a textbook on computational complexity, or an algorithms text, or just take a course on theoretical computer science?

In simple terms, problems in P can be solved in a polynomial number of operations on a computer with one processor (or with a constant number of processors), and problems in NP can be solved in a polynomial number of operations on a computer with an unbounded number of processors (or in other words, a computer which can explore an unbounded number of solutions at the same time). This is not the most rigorous definition of the classes, but it is one of the more intuitive.

The problem is this: is P a proper subclass of NP, or are there problems in NP which are not in P? The Cook-Levin theorem established the existence of "NP complete" problems, which are those which are in P if and only if P = NP.

Re:P=PN

[Anonymous Coward]

P=NP means:
"Is the set of problems solvable in polynomial time the same as the set of problems verifiable in polynomial time?"

Re:P=PN

[bunratty]

P is the set of problems that can be solved quickly. NP is the set of problems for which a correct answer can be checked quickly. Multiplication is in P and NP. Factoring is in NP, because to check that a number was factored correctly you can multiply the numbers together quickly. The question is: Is factoring (and the other problems in NP for which we don't have a quick algorithm) in P? If someone could find a quick algorithm for factoring, some cryptosystems could be easily broken.

Re:P=PN

[Yold]

My computer science is rusty, but essentially it wants to know if polynomial time solution algorithms (n^2, n^3, ..., n^c: where c is constant) exist for EVERY problem that is verifiable (solution checkable) ALSO in polynomial time.

Classic example, traveling salesman problem. Imagine you have to visit 5 cities, find the ordering of visits that yields the lowest total distance traveled. This problem is NP hard, thus it requires exhaustive search ( 5! solutions => n! time) to find an optimal solution. Verification of an optimal solution can be done in polynomial time (i.e. you already have the answer).

The cool part about P=NP, is that if ONE algorithm is found that solves an NP hard problem in polynomial time, ALL problems are solvable. You can map one sort of NP problem (e.g. traveling salesman), to another sort (e.g. 3-SAT), and have it remain NP. So if for one NP hard problem, you find a solution in P, it follows that ALL NP problems are solvable in P.

So basically it boils down to finding a holy grail of algorithms.

P.S. Apologies in advance, I haven't touched my Sipser book in 3 years.

Re:P=PN

[vlm]

P is the set of problems that can be solved quickly.

I'd take issue with that, in that P is the set of problems that scales polynomially and for simplicity people like to call that "fast" or "quick". But it can still be computationally infeasible in the real world.

My gut level assumption from being "into" this stuff for decades is we're Probably going to find out that theoretically, yes P=NP, but all the practical P solutions of NP problems unfortunately end up with crazy coefficients, such that its useless in the real world.

An example might be, a typical NP fail would be something that scales where the exponent is the problem size. What I'm talking about is a magic way will probably eventually be found to solve that NP problem in poly time, its just the polynomial constant or linear coefficient might be like a billion times the age of the universe or something like that.

There's a lot of wailing and tooth gnashing that proving P=NP would instantly permanently break all cryptosystems, like all magically and stuff with no more effort or computation required than Harry Potter waving a wand. That sort of hucksterism is an entirely separate, social, not technical, problem.

Re:P=PN

[blair1q]

So basically it boils down to finding a holy grail of algorithms.

Oh, is that all?

I think Mark Twain sussed it, then, and wrote it in allegorical form.

Just look up Tom Sawyer and whitewashing the fence.

Re:P=PN

[Anonymous Coward]

Well you have to find an algorithm that solves an NP-complete problem in polynomial time, not just NP-hard.

Re:P=PN

[bunratty]

Generally once you have any polynomial time algorithm for a problem, a polynomial time algorithm with small coefficients and small powers is found soon afterwards. This is the justification for splitting problems into P and NP. Also, the smart money is on P!=NP, but we just don't know how to prove it yet.

Re:P=PN

[Missing.Matter]

But it can still be computationally infeasible in the real world.

I think the best example that made me realize this was that O(n^100) is in P technically. But it is intractable. However, O(n^100) is still asymptotically better than O(100^n). However, algorithms that run like this are very rare... it's that large gap that exists between O(n^k) for small k and O(k^n). Always wondered why that was, but I guess if people knew we'd have a better understanding about the relationship between P and NP.

For most practical problems, O(n^3) is often intractable.

Re:P=PN

[FrootLoops]

That reminds me of a random annoyance I have with complexity theory. Why use the word "reducible"--as in "exact cover reduces to knapsack". It's more direct to just say knapsack solves exact cover. Most definitions of "reducible" I've seen use "solves" or a variant of the word. I just looked at 3 I found online and two used "solves"; the other used symbols and so avoided the word. Why include an unnecessary reversal? Maybe it's just me, but I always have to translate to make sure I'm not reversing the implication. It's just annoying, and I'm not nearly steeped in complexity theory enough for it to have become natural.

Re:P=PN

[Anonymous Coward]

First of all, your example is flawed. The optimization problem of TSP is _not_ polynomial time verifiable. However, if the question is "is there a path on less than k visiting every city", for some k, then the problem is polynomial time verifiable. Also, there are algorithms solving TSP in less than n! time by dynamic programming O(2^n * n^2) or something like that.

But yes, it is mainly the question that "if a solution to the problem P is _verifiable_ in polynomial, can we make an algorithm solving P in polynomial time?".

Re:P=PN

[Anonymous Coward]

No, NP-hard means that all problems in NP are (polynomial-time) reducible to it. Therefore if there is a polynomial time solution for an NP-hard problem all problems in NP are solvable in polynomial time.

NP-complete means that a problem is NP-hard and is also known to be in NP. While finding a polynomial time solution to an NP-complete problem would also give a polynomial time solution to everything in NP it is a weaker result, although sufficient to show P=NP.

Re:P=PN

[Anonymous Coward]

P stands for a positive number and N for negative.
What are the values of P and N such that P=NP?
Clearly, P=0 is not a solution because its not positive.

So they are looking for this number for 30 years and have not found one yet. There are so many numbers to check...
When the number is found, every encryption system will be easily decrypted by this key.

Re:P=PN

[razberry636]

You're really close!

For NP-complete you need a slight modification of the traveling salesman problem. An example would be that you need to visit 5 cities, but you need to travel less than 50 miles. Is there a route that will get you through all 5 cities in less than 50 miles?

To find a solution need to search through all the permutations (factorial time), but to verify that you have a solution is polynomial time.

However, your original traveling salesman problem is NP-hard because there is no way to verify that you have the shortest route without calculating all of the routes.

I probably have an advantage here because read the Sipser book less than a year ago. Let's see what I remember in another three years. ;)

Re:P=PN

[Missing.Matter]

I think you're using NP, NP Hard, and NP Complete interchangeably, when they are very different.

B is in NP Hard if every A in NP polynomially reduces to B, even if B isn't in NP.

B is in NP Complete if B is NP and also, every A in NP is polynomially reducible to A.

B is in NP if B can be decided in polynomial time by a nondeterministic Turing Machine.

Re:P=PN

[FrootLoops]

Perhaps you should read a textbook on computational complexity, or an algorithms text, or just take a course on theoretical computer science?

Why? I'm honestly curious. If the GP has been fine without much complexity theory, and has been out of academics for presumably over a decade, it doesn't seem worth it to bother. From the very little complexity theory I've encountered, it doesn't seem terribly useful to actual programmers unless they have a specific problem that other people have worked on. I don't mean to beat up on complexity theory. I'm a pure math person so I'm fine with theory having a low amount of practical value, where it's studied mostly for the enjoyment of those studying and sometimes out comes an application or two that might spur on grants.

Re:P=PN

[Anonymous Coward]

P type problems are solved by logic.
NP problems are solved by intuition.

To help remember which is which:
P problems are solved by people with a Penis.
NP problems are solved by people with NoPenis.

Re:P=PN

[Missing.Matter]

B is in NP Complete if B is NP and also, every A in NP is polynomially reducible to A.

And of course I mean "polynomially reducible to B" for anyone confused.

Re:P=PN

[betterunixthanunix]

Except that complexity theory does actually matter in the real world, and a solution to the P=NP problem would have broad implications in applied CS. There are quite a few situations in which we use heuristics where exact solutions would be significantly better (register allocation comes to mind, as does the place and route step for FPGAs), simply because finding an exact solution involves solving an NP-complete problem.

That most programmers do not really need to deal with complexity is really a result of most programmers not working on interesting programs.

Re:P=PN

[ObsessiveMathsFreak]

So basically it boils down to finding a holy grail of algorithms.

Or alternatively, proving that there exists a single NP hard problem for which no such algorithm exists. At least, if I read your post right.

Re:P=PN

[Anonymous Coward]

Noted, thank you for your pedantry. All that would have been easily included in the post without confusing people. The world would be a better place with more people like you in it, you must be a joy to work with...

Re:P=PN

[Yvanhoe]

I recommend looking it up. It is a notion of algorithmics that has useful practical applications even outside the realm of theoretical computer science. It can help you notice quickly which problem just requires more hardware to solve and which problem you should forget about finding the optimal solution.

Re:P=PN

[Missing.Matter]

The GP has probably only been working on problems that are in P, and in fact there are a lot of those. However, there are also a LOT of problem which are in NP we would like to solve.

Scenario 1: The classic example. You work for a presidential political campaign and your candidate asks you to plan the best possible trip to 1000 counties for the next year. The optimal trip will visit the same city only once, and in total take the least distance. This is known as the traveling salesman problem problem is NP Hard.

Scenario 2: Your boss asks you to write a program that, given a boolean formula, determines if there is an assignment of variables that makes it true. This is known as SAT, and is NP Complete.

What's more, there are even HARDER problems than these... things that take more than Polynomial space, so you would need more atoms than are in the entire universe to store the data.

And then there are problems that are IMPOSSIBLE to solve with current computers, given an infinite amount of time and space. Suppose you're writing a compiler, and you would like to warn the user that the program he wrote contains an infinite loop. This program is not Turing recognizable.

Or pretend you're an instructor for a programming course. You would like to write a program that takes in a student's homework, and compares it against a solution program, and determines if the two programs do the same thing. This would be the most amazing program in the world, but it's not even Turing recognizable!

Knowing these facts may seem academic, but if you know your problem reduces to TSP or SAT or CLIQUE, you can tell your boss this is not feasible for our input size, so we either need to relax the problem or approximate the solution. If you don't know this you're going to waste your time writing a program that takes 4 years to calculate the answer.

Re:P=PN

[FrootLoops]

its just the polynomial constant or linear coefficient might be like a billion times the age of the universe or something like that.

That would strike me as extremely strange. There are few large constants floating about in proofs. I should be clear that I'm imagining a polynomial time solution for some NP-complete problem, wherein one of the coefficients is minimized by "like a billion times the age of the universe or something like that". It would physically be a bit strange, too, seeing as a change in scale to our universe (say, much, much older) would make the constant unremarkable. Human-scale inconveniences just have no place in such abstract proofs, to my mind. My incredibly uneducated opinion is that P != NP, but that there's a good reason it hasn't been proven--like the question is undecidable in common systems of formal logic, or we're missing a big branch of thought on complexity theory in general.

P(!)=NP reminds me a little of Fermat's Last Theorem. The result most people expect is "no, it's not possible" (...to solve an NP-complete problem in polynomial time, or to find (x, y, z) positive integers where x^n + y^n = z^n for n > 2, respectively). We already knew it would be very difficult, to the point most people think it's impossible. A proof would most likely just confirm suspicions. (Of course FLT was proven, and no, it's not possible. Interestingly it was known for a while that there are at most a finite number of counterexamples for a given n, ignoring multiples, so the final proof just said this finite number is always 0. This had also already been showed for n prime up into the millions via computer, and various other special cases had been proven.)

Re:P=PN

[mog007]

Spot on, but I believe you meant NP-Complete every time you said NP-Hard.

Re:P=PN

[Missing.Matter]

Because saying "solves" removes an important implication of reducibility. When I say "exact cover reduces to knapsack" what I mean is there exists a function f(x) that maps every instance of exact cover to knapsack in polynomial time. The thing is, when we're talking about any theory, it's important to be very precise with language. What exactly does "solve" mean? Can we use knapsack to decide exact cover? Or does can we only use it to recognize exact cover? The difference between these two things in computability theory is drastic.

Re:P=PN

[Kamiza Ikioi]

Sounds right to me. It's most well known as the Knapsack Problem. It's also known as the mail carrier problem, finding the most efficient route to deliver mail.

Little did they know in 1971 that the answer was "Hire cheap labor from foreign countries". For P=NP, if P=customer service, NP = India.

Re:P=PN

[Anonymous Coward]

15 years of developing software and I still don't know what P vs. NP means.

Sad, sad old hacker.

I believe it means N=1

Re:P=PN

[Nicolas MONNET]

It might not really make much of a difference actually; what if P=NP resulted in the routing problem you mention being solvable in O(n^1000), while a probabilistic algorithm giving an acceptable result was O(n^4)?

Re:P=PN

[Anonymous Coward]

"There's a lot of wailing and tooth gnashing that proving P=NP would instantly permanently break all cryptosystems, like all magically and stuff with no more effort or computation required than Harry Potter waving a wand. That sort of hucksterism is an entirely separate, social, not technical, problem."

Well, that's a little excessive. It would probably just put to rest all of the nonsense you generally hear about "well if you built a supercomputer the size of the universe and ran it for the rest of the life expectancy of the universe it couldn't crack this cyrptosystem". (Really? You sure that sometime before the heat death of the universe, or the much, much sooner occurrence of the end of your own natural life span, we won't have a 4096-qbit quantum computer capable of factoring that key in a reasonable length of time?) Which, frankly, would be a bit of a relief.

Re:P=PN

[locofungus]

no such algorithm exists to solve an NP complete problem rather than NP hard problem.

NP hard problems are at least as hard as everything in NP but might be harder than anything in NP. For example, the halting problem is NP hard.

NP complete problems are at least as hard as everything in NP and, additionally, are in NP, thus they are the hardest possible problems in NP.

Tim.

Re:P=PN

[FrootLoops]

My question was why should the above specific programmer study complexity theory. As I mentioned, complexity theory can certainly be useful to actual programmers when they encounter a specific problem that other people have worked on. In that case it seems fine to research the relevant problem on demand, especially considering most programmers are "not working on interesting programs" anyway. To be clear, given that the OP has been fine without complexity theory and is a ways out of academics, why should they study a complexity theory or algs book, or take some theoretical CS course? "Just in case it comes up" seems like a poor answer as above. "To expand their mind" seems decent, though. I'm all for a smarter general population.

Of course I agree that complexity theory has numerous applications, mostly in specific problems and approximations. A P != NP result would represent the culmination of a huge amount of theoretical effort with few practical applications (since we've more or less been assuming it for years anyway). Those who work on the problem while believing P != NP presumably aren't motivated by real-world applications and would likely fit into my category of those who enjoy the study itself. I'm sure complexity theory has relatively fewer of those types than, say, algebraic number theory, though.

Re:P=PN

[bluefoxlucid]

Forty years of fornication is better.

Re:P=PN

[FrootLoops]

I suppose I've always assumed programmers have a feel for when their problems are particularly hard. By parallel, in math I would have expected Hilbert's 10th problem to be impossible just from hearing it. (It in fact is impossible.) I answer questions on the math sub-board of a programming forum sometimes and have gotten a few NP(-complete) problems, though they were all easily recognizable as such even with my poor background in complexity theory.

Re:P=PN

[Novus]

if you know your problem reduces to TSP or SAT or CLIQUE, you can tell your boss this is not feasible for our input size, so we either need to relax the problem or approximate the solution. If you don't know this you're going to waste your time writing a program that takes 4 years to calculate the answer.

I think you mean: "you know TSP or SAT or CLIQUE reduces to your problem". By reducing one problem to another (quickly enough; polynomial time is good for NP-completeness proofs), you can show that the problem you have reduced to is at least as hard as the one you reduced from. Lots of easy problems reduce to SAT, but SAT doesn't reduce to them. In other words, "I can reduce SAT to my problem in polynomial time. Hence, if I can solve my problem in polynomial time, I can solve SAT in polynomial time, proving P=NP. Since nobody's been able to do that in 40 years, I wouldn't bet my career on doing it."

Re:P=PN

[doshell]

Quite true. However, I do not know of a single problem in P whose optimal known algorithm is O(n^c) with c bigger than 4 or 5. (That, of course, is no proof that none exists.) Does anyone know if there is any mathematical insight for why it should be this way?

Re:P=PN

[nebaz]

Some problems are deceptive though. Think Fermat's Last Theorem.

Re:P=PN

[FrootLoops]

To me, "solves" definitely implies the decidability version. That is, given two languages A and B, "A solves B" means that there is a map f from B to A where f(x) is in A if and only if x is in B, for all possible x (not just those in B). As ever there are context-dependent restrictions on f--like it must be computable--but those are present regardless. It doesn't seem to me like "reduces" is any more or less precise than "solves".

Re:P=PN

[doshell]

Ultimately it's a matter of semantics. But it doesn't sound right to say that a problem "solves" another. Problems don't solve anything; algorithms do (on a tangent: show me a problem, and I will present you with two different algorithms for it with dramatically different run times). On the other hand, "reducible" captures the notion that you can represent the reduced problem as an instance of the problem it reduces to.

Re:P=PN

[doshell]

Nitpick: when I said "show me a problem" above, I mean of course a problem solvable with a known algorithm. Otherwise the GP might demand that I present him with two different algorithms for the Halting Problem, and I'll be stumped. :)

Re:P=PN

[FrootLoops]

FLT wasn't terribly deceptive, though. The original conjecture was proven true, and Fermat's intuition borne out as correct. Before its proof, numerous other mathematicians agreed to its truth over the years. A great many mathematicians proved special cases (Euler, Gauss, Lebesgue, and Legendre, to name a few of the most famous from the Wikipedia page; perhaps Fermat himself, though it's hard to say). I've never heard of someone who thought a counterexample would be found. The only deceptive cases I can think of for programmers are very contrived and would be recognizable as "hard" after reading the Wikipedia complexity article instead of a book.

Re:P=PN

[Missing.Matter]

Right, I always get them mixed up.

Re:P=PN

[Missing.Matter]

My favorite example of this is Shortest Path vs. Longest Path.

Shortest path is in P. The worst algorithm I think is Dijkstra's will solve it in O(V^2) for example. So you would think finding the longest path in the graph can't be much harder, right? Actually it's NP-Complete.

Re:P=PN

[FrootLoops]

Problems don't solve anything; algorithms do

I'd say similarly problems don't reduce anything; algorithms do. I expand "knapsack solves exact cover" to "if we can solve knapsack, we can turn that solution into a solution for exact cover". The mental picture that goes with that expansion is a long page of code representing knapsack, the apparently more complicated problem, and a shorter page of code representing exact cover, with a function call to the knapsack code. That image and phrase seems to capture your notion of reducibility. Of course it is just semantics, and not terribly important :). I wonder, given the choice, which terminology people first learning the concept would tend to pick.

Re:P=PN

[hubie]

Coincidentally, I have discovered a truly marvelous proof of this, which this Slashdot box is too narrow to explain.

Re:P=PN

[TheLink]

Sure it matters, but not directly. So it still does not answer the "why".

Research on nuclear fusion power plants might matter in the real world, but since the solution does not exist yet, most power plant designers or builders do not need to take up courses on it.

If a very smart person solves the P=NP problem and publishes the result, the programmers will soon be able to look up the resulting solutions on Google.

No need to: "read a textbook on computational complexity, or an algorithms text, or just take a course on theoretical computer science".

Saying that a programmer should do all that is like saying that a house designer/builder should take a course on theoretical material science.

Once a new construction material becomes actually available in practice then it makes sense to know about it. Otherwise it's not really useful.

Of course one can still learn about it out of curiosity.

Re:P=PN

[Missing.Matter]

I answer questions on the math sub-board of a programming forum sometimes and have gotten a few NP(-complete) problems, though they were all easily recognizable as such even with my poor background in complexity theory.

Right, that's probably reasonable as long as you are well versed in maths, you can probably infer a lot of complexity theory (which in the end is evaluating and comparing asymptotic behavior of functions). Where I think complexity theory would help is in understanding just why the problem is hard, how it relates to other problems, which could lead you do a very nice way to relax or approximate the problem.

Re:P=PN

[FrootLoops]

No, it's alright, I was able to coerce it into a true statement regardless. The restriction that you use a Turing machine, while common, is only implicit. Since that doesn't make sense, you clearly must not have been working with that restriction. So, given an unrestricted algorithm to solve a problem, you can just assume it's running on a machine capable of instantly solving that problem. You can then take the first algorithm to be trivial. The second algorithm with the drastically different run time could be done by inserting a useless but long loop depending on input size. Done!

Re:P=PN

[Arancaytar]

Because programming and computer science are two barely related endeavors. You could learn complexity theory without ever learning to code in anything but BASIC.

Re:P=PN

[russotto]

Quite true. However, I do not know of a single problem in P whose optimal known algorithm is O(n^c) with c bigger than 4 or 5.

Primality, c = 6.

Re:P=PN

[Missing.Matter]

That is, given two languages A and B, "A solves B" means that there is a map f from B to A where f(x) is in A if and only if x is in B, for all possible x (not just those in B).

You pretty much just stated the definition for a reduction. I mean, if all you have is a problem with the word then I guess all you risk is confusing people who aren't familiar with your terminology.

I remember being introduced to the concept of reductions with the following analogy: Say I want to go to my friend's house.This is easy if I have his address, otherwise I would need to visit every house until I found his. So the problem of going to my friend's house reduces to knowing his address. But just by knowing his address, I'm not at my friend's house; I still have to do the actual work of walking there. To me, saying that A solves B in this context is like saying knowing my friend's address gets me to his house. Whereas in reality, knowing his address gives me a path for me to walk which when followed will lead me there.

(Actually, if I don't know the area this problem probably further reduces to finding a map.)

Re:P=PN

[doshell]

I agree that "A reduces to B" is equally nonsensical; it's an artifact of a growing (and sometimes irritating) tendency to suppress passive clauses in English. The passive version, "A is reducible to B", is more in agreement with my reasoning, since it doesn't convey the idea that the reduction is performed by A.

My problem with viewing problems as "pages of code" is that there is no one-to-one correspondence between problems and programs for solving them. I would rather view an algorithm as a machine where certain problems fit, but others don't. (Imagine one of those things used to teach shapes to children.) "A is reducible to B" implies that, although A does not fit in any machine where B fits, there is a machine that can transform an instance of A into an instance of B ("bend its shape") so that it may be solved by any machine for B.

But of course no one has to have the same mental image that I do. :)

Re:P=PN

[TheLink]

All that is still mostly irrelevant.

People write imperfect programs to imperfectly solve problems all the time, and often the customers are happy enough with the imperfect results to pay good enough money. And at least some of the time they aren't really being swindled ;).

For example, the famous "halting problem" is actually an easier problem than detecting that a given program is malware (yes I know the halting problem is impossible to solve over turing machines, but bear with me).

The halting problem can be stated as "given a program and an input, figure out whether the program will eventually halt or will run forever."

Whereas an antimalware program just has a suspect program but not the full inputs, nor even the full program - it might connect to a server on the internet for legitimate reasons (updates) or not (malware payload/instructions). And sometimes the determination of malware might even be subjective.

So it is impossible for the antimalware program to work perfectly but that does not stop many people from using them, or even willingly paying for them.

BTW if one wanted better security the operating system would require the program to do the equivalent of requesting upfront what the program wants to be able to do. And then use that to help the user make a better decision on whether to actually run the program or not. And the operating system enforces the limits.

This is in effect sidestepping the halting problem by having the program say upfront how much time it wants, and if it tries to run beyond that time, the OS halts it ;).

I believe some phone OSes do something like that already.

Re:P=PN

[doshell]

Yes. If anyone were to challenge me to prove my assertion, prepending a useless long loop depending on input size at the beginning of a valid algorithm would be my answer. :)

Though I still have a problem with the other part of your post. Suppose I am allowed to assume the trivial algorithm exists; I cannot however assume anything about its complexity (that would be cheating). So, assuming that by "drastically different run time" I mean to say that they're not big-O equivalent, I am stumped when deciding how big to make the initial, useless loop; for, for any complexity that I might choose for that initial loop, it may be the case that the trivial algorithm already has at least that complexity. ;)

Re:P=PN

[Darinbob]

Actually, if you have to visit 5 cities that is O(1). That's because in your case "n" is a constant. Nothing like nitpicking to start off the day right.

Re:P=PN

[doshell]

Thanks :) But the essence of my point stands: do you know of any example for c=7, then?

Re:P=PN

[Surt]

http://en.wikipedia.org/wiki/P_versus_NP_problem

To oversimplify, it boils down to the fact that we have noticed that there is a set of problems where, if you have a potential answer, you can quickly (and by quickly: in an mount of time defined by a polynomial ... e.g. O(n^2)) verify whether or not it is correct.

But: there is no known way to find that answer quickly (in polynomial time). Instead, we are typically talking about problems where the best known solver algorithm takes exponential time (O(2^n)).

P vs NP boils down to wondering: do we just suck at coming up with algorithms (P=NP), or is it genuinely impossible to solve said problems in polynomial time (P!=NP)

Re:P=PN

[Nicolas MONNET]

Primality of n numbers?

Re:P=PN

[Missing.Matter]

You could learn complexity theory without ever learning to code in anything but BASIC.

I recently took two courses, one in algorithms another in theory of computation. I didn't write a single line of code for either. That's the way it should be, because algorithms are language agnostic (as long as they are Turing complete).

Re:P=PN

[Anonymous Coward]

All fields of science needlessly make things more complicated with language and mathematical bullshit. As far as I can tell, it's done for two reasons: 1. to formalize the discussion, which is a legitimate reason, and 2. to construct artificial barriers to understanding, so people steeped in the mess they create can feel special. The gatekeepers are the learn-ed men of educational institutions, and if you want to be a part of their club, you have to learn their language. It's a hazing ritual.

Re:P=PN

[guyminuslife]

Find the sum of two X-dimensional matrices, with N elements along each axis. Should be O(N^X).. E.g., summing the corresponding values in two 1-dimensional arrays of length N should take O(N) time, summing the corresponding values in two square NxN matrices should be O(N^2), if they're "cube" matrices it should be O(N^3), et cetera.

I think the insights you're looking for aren't mathematical, they're practical.

Re:P=PN

[Jonner]

I can't say I understand the issue either, but I wish I did. What this illustrates is Computer Science is quite distinct from software development and programming, though many conflate them. You don't have to know much physics to be a technician or do most engineering either.

Re:P=PN

[Anonymous Coward]

Disclaimer: I' m NOT a mathematician (nor do I play one on TV).

I read thru the wikipedia article and two items struck me:

        "An answer to the P = NP question would determine whether problems like the subset-sum problem that can be verified in polynomial time can also be solved in polynomial time. If it turned out that P does not equal NP, it would mean that there are problems in NP (such as NP-complete problems) that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time."

and, if P=NP were proven:

"But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. According to Stephen Cook,[15] ...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems."

Based on the 1st quote, if P does NOT equal NP then NP-complete problems CANNOT be solved in polynomial time.

Based on the 2nd quote, complex mathematical proofs are examples of solutions to NP-complete problems. Doesn't this equate to a very small subset of humanity solving a handful of NP-complete problems in polynomial time? How is this explained if P does NOT eqaul NP? Do human "intuitive leaps" somehow fall outside computation limitations?

Re:P=PN

[guyminuslife]

Now that I think of it, that's probably not right. You'd have to have an input size I=2 * N^X, and then the algorithm would take O(I) time.

Re:P=PN

[pthisis]

Suppose you're writing a compiler, and you would like to warn the user that the program he wrote contains an infinite loop. This program is not Turing recognizable.

If I'm writing a compiler for an existing computer--or one that will ever exist--then it is, in fact, Turing recognizable. The Halting problem is theoretically decidable (and hence the infinite loop half is Turing recognizable) for all real-world computers. It's only undecidable for a theoretical Turing machine that has infinite space. See, for instance, Marvin Minsky, Computation, Finite and Infinite Machines (1967).

I believe that given the finite resources in the universe it is impossible to actually construct a computer for which the Halting problem is not decidable (though it may be practically intractable).

Re:P=PN

[Anonymous Coward]

Well, there are approximation algorithms to NP-hard problems, including the travelling salesman problem on a planar graph, that can guarantee a solution within a factor of epsilon of optimal, if given O(p(n)*1/e) time, where p(n) is a polynomial of the input size n. On the other hand, such algorithms are not really practical - they are of theoretical interest only.

Re:P=PN

[lgw]

Hoiw useful could an algorithms class possibly be if you didn't actually write any algorithms? Perhaps you wrote lines of code, just not in any real-world programming language? That's not a good thing, BTW - recent CompSci graduates really seem to need more experience in hands-on coding.

Re:P=PN

[Missing.Matter]

I said we didn't write code, not algorithms. I think the distinction is warranted, since algorithms existed well before programming languages. As for computer science graduates needing more programming, I don't know whether that is true or not, but it's not the job of a theoretical algorithms course to teach programming or lend experience in programming. For what it's worth this was a graduate level course; I don't know what they do at the undergraduate level.

Re:P=PN

[oliverthered]

looking at Wikipedia it would appear that new thing in this article is that it may be possible to show that Tautology problems (or possibly just one of them) can only be checked in NP-complete not P that is the solution only reduces the harness of the problem to NP-complete but not to P.

Re:P=PN

[oliverthered]

the reason (taking the dictionary definition) is that Tautology is saying the same thing in two different ways.... a bit like: this is not an example.

but more like 'I went over the bridge not under the bridge'

Re:P=PN

[dkf]

If the maximum length of Hamiltonian path is polynomial in the number of cities, and you have a polynomial "get a path shorter than k", then you can can apply that polynomial algorithm a polynomial number of times (i.e., a polynomial operation) to get a series of approximations to the best path. The proof is easier with integral distances.

Re:P=PN

[morgaen]

Let's hope it's not your last one!

Re:P=PN

[praxis]

Are algorithms and code differentiable?

Re:P=PN

[Anonymous Coward]

Why did I read that as "My computer science is Lusty".

Re:P=PN

[Anonymous Coward]

B is in NP Complete if B is NP and also, every A in NP is polynomially reducible to *B*

Correction at the end of sentence. Right?

Re:P=PN

[lgw]

Did you write down an algorithim is an unambiguous way? Yes? Then you wrote code. No? Then that was one worthless class. Assuming you did write code, it's a shame you didn't write that code in a common programming language where the experience of running and debugging it would have been useful in later life.

Re:P=PN

[TheGratefulNet]

if you write real code for everyday things, you'll never run into this.

unless you interview at google. and then, this stuff is mostly what they care about. (sigh).

the 'google disconnect', that is. their view of reality is highly distorted.

Re:P=PN

[Anonymous Coward]

I did my job just fine before I visited the Louvre. I'll do it just fine now that I've been there, but I'm still glad I went.

Re:P=PN

[Missing.Matter]

I guess if you consider rough pen/paper pseudocode outlines of algorithms well above the implementation level to be coding, I guess I did some coding for a few homework assignments. Honestly spent more time on proving complexity and proofs of correctness. As for your concern with my academic development, I appreciate it I guess, but I don't feel I have much to gain from physically implementing quicksort when I'm already coding 12+ hours a day.

Re:P=PN

[lgw]

If your university has you coding 12 hours a day that's great - which one? I find that shocking for an American undergrad program. If you're coding at a job/internship, that's great for you (internships are the best thing you get out of college, career-wise), but not so much the school.

BTW, implementing quicksort once ever in life is important to seed your (or at least most people's) brain's pattern recognition with important primitives. Much like writing detailed notes helps most people remember the content of a lecture, even if they never refer back to those notes, actually coding quicksort might help you 10 years later to realize "oh, wait a second, this thing I'm writing is really just quicksort, I don't need to write this", which isn't always so obvious in the design phase. Of course, that's only if you're lucky enough to find a "real" coding job, but that's a different topic.

Re:P=PN

[Missing.Matter]

I think you missed where I said this was a graduate level course; I'm in a PhD program. I'm guessing they either figure we've seen this stuff at least briefly once before, or we'll do what we need to do outside of class in order to understand it. I don't know how they treat the undergraduate version.

Re:P=PN

[JimFive]

Doesn't this equate to a very small subset of humanity solving a handful of NP-complete problems in polynomial time?

No. First of all, I'm not sure that I agree with the statement that mathematical proofs are good examples of NP-complete problems. Secondly, NP does not mean Not polynomial. It means Non-Deterministically polynomial. So what the quote indicates is that a small subset of humanity solved some NP-complete problems non-deterministically.

How is this explained if P does NOT eqaul NP? Do human "intuitive leaps" somehow fall outside computation limitations

Yes. Humans are not Turing machines. The big technical difference between P and NP is that P are solvable in polynomial time on a Deterministic machine, while NP are known to be solvable in polynomial time on a Non-Deterministic Machine.
--
JimFive

Re:P=PN

[FrootLoops]

Actually, I meant to assume your machine, as one of its basic operations, can solve the given problem. That is, usually "addition" is a fundamental operation, though a more powerful machine might have "solve the traveling salesman problem" as an "assembly instruction". This is slightly less trivial than it at first might sound. If your machine has dedicated hardware to compute FFTs, and your problem is solved trivially by an FFT, there is a trivial O(1) algorithm for it on that hardware. Interestingly, you can even drop the assumption that your problem is (Turing-)computable, since this magical machine might well be powerful enough to compute things no Turing machine can. Ignoring this assumption, say you have an O(f(n)) algorithm to solve your problem. One way to make an algorithm of strictly (in O-terms) worse runtime is to just run that algorithm O(n) times, ignoring the solution every time but the last. [This is in fact strictly worse: for O(n f(n)) = O(f(n)) means there is a c such that for all n large enough n f(n) is less than c f(n), which makes no sense. Slightly informally, O(f(n)) = O(g(n) f(n)) if and only if g(n) is bounded.]

Re:P=PN

[FrootLoops]

Oh, sorry I wasn't clear. Yes, my problem is entirely with the word. Specifically, I'd prefer "A reduces to B" to be said as "B solves A". I know it's unimportant, but it's always bugged me (probably more than it should). You make a good point about "solves" possibly implying the solution is completely direct and doesn't require any additional steps. I'm probably much more comfortable with existence results than most CS people, and I use the same mental routines to process them as I do the phrase "B solves A", so the possible indirectness doesn't affect me much. In any case, thanks for humoring me :).

Re:P=PN

[doshell]

Ignoring this assumption, say you have an O(f(n)) algorithm to solve your problem. One way to make an algorithm of strictly (in O-terms) worse runtime is to just run that algorithm O(n) times, ignoring the solution every time but the last. [This is in fact strictly worse: for O(n f(n)) = O(f(n)) means there is a c such that for all n large enough n f(n) is less than c f(n), which makes no sense. Slightly informally, O(f(n)) = O(g(n) f(n)) if and only if g(n) is bounded.]

Yes, you're totally right. I was overlooking that possibility.

Nice discussion, thanks!

Re:P=PN

[doshell]

Since in the original problem n is the prime number whose primality is to be determined, I'm not sure what you mean. Taking a liberal interpretation, n repeated applications of the algorithm do indeed take O(n^7) time, but since the input size has also grown by a factor of n, the overall complexity remains unchanged at O(n^6).

Re:P=PN

[Anonymous Coward]

That reminds me of a random annoyance I have with complexity theory. Why use the word "reducible"--as in "exact cover reduces to knapsack". It's more direct to just say knapsack solves exact cover. Most definitions of "reducible" I've seen use "solves" or a variant of the word. I just looked at 3 I found online and two used "solves"; the other used symbols and so avoided the word. Why include an unnecessary reversal? Maybe it's just me, but I always have to translate to make sure I'm not reversing the implication. It's just annoying, and I'm not nearly steeped in complexity theory enough for it to have become natural.

Because knapsack isn't any sort of object with volition or motivation. It can't solve anything.

So?

[CTU]

am I the only person who does not get what this means? What does p=np mean and why is it inportaint?

so P=9 and N=1

9=1*9 Solved lol

Re:So?

[sakdoctor]

Are you the only person who couldn't be bothered to look it up?

http://en.wikipedia.org/wiki/P_versus_NP_problem

Re:So?

[gnick]

Exactly - Divide both sides by 'P' and it reduces to 'N=1'. So, P=NP iff N=1. People who spend so long on this debate must not be very good at math... =)

Re:So?

[vlm]

am I the only person who does not get what this means?

The most non-mathematical way to express it, probably somewhat innacurately, is the fastest way to figure out if you can learn what "p=np" means is for you to figure out what "p=np" means and then see how long it took.

Its also used as a stereotypical filter... If you know what it is, you're somewhere on the "computer science" path. If you don't, even if you don't know it, you're on the "IT" "IS" or "code monkey" path. It's almost as accurate as asking someone if they've heard of a programmer named "Knuth".

If you're involved in any problems similar to any on this list:

http://en.wikipedia.org/wiki/List_of_NP-complete_problems

and you've ever thought about scalability, then you're at least on the path to understanding P=NP

Re:So?

[Ambitwistor]

P vs. NP for dummies

Re:So?

[doshell]

Actually, it's not an iff. If P=0 then P=NP no matter the value of N. ;)

Re:So?

[Anonymous Coward]

Do you like to have your files, HTTPS sessions, etc encrypted? Yes? You want it to be hard to crack that encryption? Yes? Then you care that P != NP.

Re:So?

[Anonymous Coward]

That's the easy part - the 'age old question' is how can we write a computer program that can find ALL the solutions to this problem in a reasonable amount of time. Verifying that 9, or 2, or pi, is easy, but finding a true solution to the equation is what this deals with.

Re:So?

[Anonymous Coward]

Your math gets a failing grade. You missed the solution where P=0 without any constraint on N.

Re:So?

[JoshuaZ]

Do you like to have your files, HTTPS sessions, etc encrypted? Yes? You want it to be hard to crack that encryption? Yes? Then you care that P != NP.

Although note that encryption being hard is generally a much stronger claim than P != NP. All known encryption systems that rely on complexity conjectures need stronger claims than P!=NP. Thus for example many rely on the difficulty of factoring integers into primes. It is possible (although it seems unlikely) that P != NP but factoring is still in P. The reason to care about P ?= NP in an encryption context is that if P = NP then encryption definitely doesn't work. But the other direction isn't necessarily the case.

Re:So?

[betterunixthanunix]

All known encryption systems that rely on complexity conjectures need stronger claims than P!=NP.

This is not technically true; some cryptosystems based on lattice problems have security reductions to NP-hard problems and ultimately rely only on P!=NP.

Re:So?

[Anonymous Coward]

Sigh....

It's actually a pretty simple concept but you do need to be familiar with the jargon:

P and NP are "complexity classes" meaning they're short hand for a formal definition of large groups of computable problems. There are many complexity classes but P and NP are two particularly important ones because modern cryptography is based on the premis that they are not the same (which seems likely even though it has never been proven true).

Modern cryptographic approaches require the concept of a "trap door" function. That is it's sufficiently more computationally costly to generate a valid solution than it is to verify that the solution is correct. This means that if P!=NP you can have your decryption algorithm be P and you key generation algorithm be NP, and in order to crack a key of any given complexity, the cracking computer would need to be exponentially more powerful than than was necessary to use the key (so you'd need a super computer to crack your cell phone's encryption for example).
If however P=NP than there's no way to guarantee that your cryptography program can't be cracked on a computer only marginally more powerful than the one using the key (say you need an i7 to crack the keys that were reasonable on an i5)

Re:So?

[vlm]

The reason to care about P ?= NP in an encryption context is that if P = NP then encryption definitely doesn't work.

Not true at all. Encryption works if, on average, it takes too long to break it using current technology for the data to be useful once its finally broke. Its an engineering balance, not a theoretical process.

P = NP is a scalability problem where it seems a very small amount of work and very small amount of key is very hard to break.

Something like DES scaled down to 8 bit keys (uh, good luck scaling the s-boxes down, but you get the general idea) is a horrible engineering decision regardless of how scalable the theoretical design is. One of 256 keys will give you your plain text english words back.

If P=NP the days of using a simple algorithm with a tiny key to protect huge amounts of data is over, but that doesn't mean crypto is dead. It just means maybe you need billion bit keys for an engineering win instead of thousand bit keys for an engineering win, and you'll have to pay more attention to improvements in processor speed and parallel processing. It hardly means its "magically" dead.

Think of it in chemical terms : proving N=NP is a chemist proving a formula exists. "breaking crypto" is more like a chemical engineer figuring the appropriate limiting reagent and reaction rate kinetics using the previously mentioned formula as a tool. If the chemist figures out a new formula, worst case scenario is the engineer has some late nights of work, not unemployment.

Re:So?

[Anonymous Coward]

some cryptosystems based on lattice problems have security reductions to NP-hard problems and ultimately rely only on P!=NP.

But then again, NP-hardness only means that for every n, there is an m > n such that a "hard" instance of the problem of size m exists. There are NP-hard but insecure cryptosystems.

Re:So?

[ThePangolino]

One my think some Wikipedia articles need a tl;dr
This guy did it pretty well.

Re:So?

[betterunixthanunix]

Provably secure cryptography is about scalability, and proving the infeasibility of solving particular problems. Unlike many block ciphers, whose security is stated in terms of statistical tests, cryptosystems like RSA and ElGamal have security stated in terms of reductions to problems that are believed to be infeasible (and if we could show P!=NP, then we could have cryptosystems that are reducible to problems that are infeasible). Public key cryptography is not an engineering problem, it is a theoretical CS (or perhaps we can just say "math") problem.

Re:So?

[gnick]

D'oh! Maybe that's why people are having such a hard time with it. Should have subtracted P from both sides getting P(N-1)=0. OK, solving P=NP took me two tries - Now I understand the debate.

Re:So?

[Anonymous Coward]

40 years of these exact same jokes, and the exact same corrections, every time Slashdot runs a story on P and NP....

- curmudgeon

Re:So?

[mark-t]

Every time there is a P vs NP story on slashdot, invariably there is at least one person to make a comment like this... and every time, I see comments like this modded up as amusing. Am I the only person on slashdot who has long since ceased to find it funny?

'P' stands for "polynomial", and 'N' stands for non-deterministic. Neither side of the equals sign actually represents any single value... rather, they each represent what are typically considered to be separate classes of problems.

To assert that P = NP is to assert that problems which are provably NP hard can actually be solved in polynomial time on the same architecture on which they are supposed to be NP, and therefore NP does not, in strictest sense, exist.

It would spell the end of virtually all currently used forms of encryption, but would open up entirely new types of problems that we could get computers to solve that are currently considered wholly infeasible.

Please... how hard is it to Google?

Re:So?

[Anonymous Coward]

And this right here is a perfect summation of why negroids never excel in the maths or sciences.

Re:So?

[serviscope_minor]

Am I the only person on slashdot who has long since ceased to find it funny?

No. It was funny once, a very long time ago. Perhaps. Well maybe slightly amusing a very long time ago. It's getting pretty annoying these days.

Re:So?

[koreaman]

So if I find an O(n^{100000th Ackermann number})
algorithm for factoring integers, it means encryption is suddenly unsafe? Your understanding of this issue is very flawed.

Re:So?

[bunratty]

No, but I think a Beowulf cluster of those posts would be absolutely hilarious!

Re:So?

[FrangoAssado]

I used to think that, too, but actually the grandparent is right: all cryptosystems invented so far rely on something more than P!=NP.

It's true that some cryptosystems reduce to NP-hard problems, but that doesn't mean they rely solely on P!=NP to be secure.

The problem is that when you have a NP-hard problem, that doesn't mean that all its instances are hard to solve. For a cryptosystem based on NP-hardness, this means that not all messages are hard to decode, only that there exists at least one message that is hard to decode. To prove the system is really secure, you need to rely on some other assumption, or you'd need to find a way to use only instances of the NP-hard problem that are actually hard, and there's no known way to do that yet.

Also, lattice-based cryptography is not known to be NP-hard: as far as I understand, to break it you must find an approximate solution to SVP, you don't need to solve it exactly (which would be NP-hard). Still, it's believed that lattice-based cryptography it's harder to break than factoring.

For more information: http://stackoverflow.com/questions/311064/are-there-public-key-cryptography-algorithms-that-are-provably-np-hard-to-defeat

Re:So?

[lgw]

Everything practical is an engineering problem. Factoring could be in P and still be infeasible, for many different reasons. Factoring could be in NP and stil be feasible, for many different reasons. P vs NP is just one important factor in the feasiblity of an attack.

Also, there's no such thing as a "provably secure" cryptosystem - what rubbish! The very idea of "provably secure" is wrong-headed in any sort of security (digital or phisical).

  (BTW, the NSA has been deprecating product-of-primes based crypto for many years now, and it shouldn't be used for new work).

Re:So?

[betterunixthanunix]

Everything practical is an engineering problem

The engineering problem with theoretical cryptography is in implementing it, not in designing it.

Factoring could be in P and still be infeasible

That depends on your definition of "infeasible."

Factoring could be in NP and stil be feasible, for many different reasons

Only if factoring is also in P, or if you have some other definition of "feasible."

Also, there's no such thing as a "provably secure" cryptosystem - what rubbish

"Provably secure" has a specific and well understood meaning in the cryptography research community. It means that if a cryptosystem can be cracked in polynomial time in its security parameter, then a (assumed to be) hard problem could also be solved in polynomial time. If one could show that there is no polynomial time algorithm for the RSA problem, then the RSA cryptosystem would be secure against any polynomial time attack. Since the commonly understood definition of "feasible" is "polynomial time," this would mean there is no feasible attack on RSA.

(BTW, the NSA has been deprecating product-of-primes based crypto for many years now, and it shouldn't be used for new work).

Actually, the NSA has been deprecating all cryptography based on the hardness of problems on the multiplicative groups of integers modulo X, which includes RSA and the non-elliptic curve versions of DH and ElGamal. The reason for this is the necessity of large public keys to maintain the same margin of security as a symmetric cipher, due to the state of the art attacks on the factorization problem (GNFS) and the discrete logarithm problem, which run in subexponential (but still superpolynomial) time. The NSA has been pushing for elliptic curve cryptography because of the promise of smaller key sizes, although the attacks on those cryptosystems are also subexponential (but square root instead of cube root).

Re:So?

[lgw]

The engineering problem with theoretical cryptography is in implementing it, not in designing it.

Of course it is - that's the important part.

No one ever attacks a secure system by attacking the math of the crypto algorithm (unless the "algorithm" is only a marketing ploy). You attack the weak points of the system: the key management, or the users. You decrypt Osama's hard drive by waiting for him to decrypt it, then kicking down the door and shooting him in the face.

Factoring could be in P and still be infeasible.

That depends on your definition of "infeasible."

Of course it does. Real world computers behave differently from whiteboards. Polynomial time can still be really bad, or have unattainable resource requirements (even if you measure computer time in acre-weeks).

Factoring could be in NP and stil be feasible, for many different reasons

Only if factoring is also in P, or if you have some other definition of "feasible."

http://xkcd.com/538/ or if the key size is too small, or if the user clicks on CoolProgram.exe, or one of the many other attacks that ignore the math work.

"Provably secure" has a specific and well understood meaning in the cryptography research community.

Funny how security professional constantly rail against the very idea. "provably NP-complete", sure, but "secure"? Nonsense.

Re:So?

[betterunixthanunix]

Funny how security professional constantly rail against the very idea. "provably NP-complete", sure, but "secure"? Nonsense.

You yourself said it:

No one ever attacks a secure system by attacking the math of the crypto algorithm

The math is what is provably secure, and that is what cryptography is about. If you implement a cipher badly, it is not the cipher that is insecure, it is your implementation of it (or perhaps we might say that you did not really implement the cipher; Sony was not really using ECDSA for the PS3, since ECDSA requires a random number to be generated for every signature).

As for security professionals...well, I have spoken to many of them, and the almost universal answer I have received is this: security engineering is not cryptography, cryptography is not security engineering. Cryptography is a piece of the security engineering puzzle, and provably secure cryptography is a piece of that piece, but there is more to security engineering than that. The security of a system often goes beyond the ability of an adversary to guess a message or compute a forged signature; cryptography is not the be-all and end-all of security engineering.

http://xkcd.com/538/ or if the key size is too small, or if the user clicks on CoolProgram.exe, or one of the many other attacks that ignore the math work.

None of this has anything to do with cryptography. Small key sizes are irrelevant in security proofs; the point of the proof is that you can always select a key size large enough to protect against an adversary, without incurring an infeasible computational cost for encryption/decryption (or whatever your cryptographic primitive happens to be). Determining a proper key size -- one that is small enough to be practical but large enough to maintain a particular security margin -- is an implementation issue, and falls outside the scope of theoretical cryptography. Beating someone with a wrench falls way outside of the scope of cryptography (even applied cryptography) and is essentially in the same category as a user downloading a trojan horse: users betraying their own security. A security proof has the underlying assumption that the users are knowledgeable and will not undermine their own security (this is a common point of contention when it comes to deploying cryptosystems in "the real world," since most computer users are not knowledgeable and are often unaware that they are undermining their own security; this is beyond what cryptography alone can provide an answer for).

Ultimately, the point is that cryptography can only offer answers up to a particular point, and "security" in the context of cryptography is bounded by that point. What cryptographic security proofs offer is assurance that a cryptosystem is not the weak link in a large security system; security engineers can spend their time worrying about other problems (composing different components without compromising security, ensuring that users do not leak keys, etc.) and not worrying about attacks on the cryptosystem itself (at least that is the idea; in practice, the difficulty of proving a lower bound on a problem's complexity can result in situations like the one facing RSA, where key sizes wind up becoming larger and larger to the point where the system begins to lose its practical advantage).

non-droids in deeper water than ever?

[Anonymous Coward]

all the fake (stingy fatal) 'math, science' & religion' in the wwworld, will not cipher to any reasonable conclusions, because of failures to acknowledge the progression of our dna, increased conscience & awareness, new babys etc... makes it all look like the failing fictional foibles of flashy fake neogods, losing their lightning rods.

Re:non-droids in deeper water than ever?

[AkkarAnadyr]

Pass it on down, dude, don't sit there slobbering on the end.

And the corollary...

[errxn]

YP != MP

Re:And the corollary...

[MadKeithV]

Hah, MP > YP.

If you just paste and copy

[Anonymous Coward]

then add at least a pointer to the source.

P = NP?

[Yuioup]

Slashdot seems to have a hard-on for this topic:

http://science.slashdot.org/story/10/08/08/226227/Claimed-Proof-That-P--NP
http://science.slashdot.org/story/11/01/20/1546206/Polynomial-Time-Code-For-3-SAT-Released-PNP
http://science.slashdot.org/story/11/02/28/149244/No-P--NP-Proof-After-All?from=rss
http://science.slashdot.org/story/10/08/11/0239209/Possible-Issues-With-the-P--NP-Proof
http://science.slashdot.org/story/10/09/10/1847245/How-the-Web-Rallied-To-Review-the-P--NP-Claim

Can anyone explain what all the fuss is about ?

Re:P = NP?

[vlm]

Can anyone explain what all the fuss is about ?

Its strongly related to the "CS" vs "IT" division amongst "computer people". Its hard to find a topic that more strongly shows the separation.

The "IT" guys simply don't care (look at many of the posts in this article) but for the "CS" guys its proof would be pretty close to the ultimate "super bowl win" or "moon landing" or "date with a girl" moment.

Re:P = NP?

[PhilHibbs]

"Can current 'strong' encryption be cracked by factoring large numbers quickly?"

Re:P = NP?

[betterunixthanunix]

The P = NP problem is one of the most important open questions in complexity theory, and a solution to it would have broad implications. For example, if P!=NP, then we would have provably secure cryptography without having to assume as much as we currently do (in layman's terms: cryptography would be a bit easier to "get right"). If P=NP, then a lot of important problems could be solved efficiently (e.g. the travelling salesman problem, the place-and-route problems, etc.). Additionally, a P!=NP proof would likely involve yet-unknown techniques of proving lower bounds on the complexity of problems, as well as providing a straightforward method of proving lower bounds on the complexity of some problems.

Re:P = NP?

[Tyler Durden]

Can anyone explain what all the fuss is about ?

Seriously? Cultivate a sense of intellectual curiosity and look back at that question. The point when you've already answered it for yourself.

Re:P = NP?

[betterunixthanunix]

Note that the RSA problem is not known to be NP-complete...

Re:P = NP?

[PPH]

Its the basis of the argument that our CS people gave us as to why a natural language recognition system could not be developed. So a couple of flight control (mechanical) engineers sat down and wrote one.

Re:P = NP?

[Tyler Durden]

Right. But it is known to be in NP. So proving P=NP would prove that RSA could be cracked quickly. But proving P!=NP would not prove that RSA cannot be cracked quickly.

Re:P = NP?

[bigstrat2003]

Eh... I have a sense of intellectual curiosity, but I just cannot be bothered to give a fuck about this topic. Not caring doesn't imply I have no interest in learning things.

Re:P = NP?

[betterunixthanunix]

Right, which is why the problem is more than just, "Can integers be factored efficiently?"

Re:P = NP?

[martas]

It's not just /. that has a hard-on for it. In the entire computer science community, this problem is probably almost universally recognized as the most important open question in CS theory. Actually, the problem is considered extremely important not just in CS, but in all of mathematics: for example, see http://en.wikipedia.org/wiki/Millennium_Prize_Problems .

Re:P = NP?

[Anonymous Coward]

No, there are complexity classes like BPP whose problems can be solved efficiently, but which are between P and NP. So if P!=BPP=NP then your encryption would still be broken.

Re:P = NP?

[Anonymous Coward]

Slashdot seems to have a hard-on for this topic:

Can anyone explain what all the fuss is about ?

That's what she said.

Re:P = NP?

[betterunixthanunix]

"Without having to assume as much as we currently do."

Re:P = NP?

[steelfood]

"date with a girl" moment.

And prostitution doesn't count.

Re:P = NP?

[vlm]

Its the basis of the argument that our CS people gave us as to why a natural language recognition system could not be developed. So a couple of flight control (mechanical) engineers sat down and wrote one.

An excellent example of science "vs" engineering.

The scientists say a theoretically perfect system cannot be made. Also true that the abstract concept of a metal cube exactly one inch on a side cannot exist, because of various quantum and thermodynamic reasons there will always exist a variation somewhere deep in the decimal points.

The engineers, however, are perfectly able to make ones that "work well enough".

The hop from theory to engineering that happens with P=NP is almost as funny/interesting to talk about as the second hop on the same topic from engineering to mass media.

Re:P = NP?

[betterunixthanunix]

"I have a sense of intellectual curiosity, but I just cannot be bothered to look up the meaning of one of the most important open problems in theoretical computer science, for which a solution would have broad impacts in both theoretical and applied CS and would represent a major step forward in technology."

Re:P = NP?

[stoicfaux]

I'll take a stab at explaining the excitement with a really, really, really, tremendously bad analogy.

If you could build a warp drive (something that bent space) in order to cross vast distances quickly, then it should also, in theory, be capable of time travel (since time and space are interrelated.) Showing N=NP is analogous to proving that a warp drive would allow time travel. This would mean that Captain Kirk (or any other captain of a warp capable starship) is a Time Lord.

If you can show that N=NP, then *all* of those really hard, can't be solved with a million computers performing a million operations per second in a million years, would instead be solvable by a million computers performing a million operations per second in a few hundred years or faster.

Re:P = NP?

[Anonymous Coward]

But you care enough to make a post on slashdot saying you don't care?

Re:P = NP?

[Anonymous Coward]

Then they didn't understand what NP != P is actually about or you didn't understand their argument.

Re:P = NP?

[bigstrat2003]

I know what it means. I just don't give a fuck. It's a boring problem that doesn't spark any interest in me at all.

Re:P = NP?

[maxume]

So maybe he is a plumber or designs airplanes.

His main claim was that he was not interested in the topic.

Re:P = NP?

[Anonymous Coward]

Proving it either way is intresting, becouse if p=np you can start internets terrorist career with unseen success... or if you prove it other way you'll get million cash award anyhow and prolly job from any techcompany/university if you play your cards right...

Re:P = NP?

[Anonymous Coward]

Ok, so you don't give a fuck, you're edgy, we get that. You can't see "what all the fuss is about" though?

Re:P = NP?

[Anonymous Coward]

It all comes from Cobham's thesis, which is that "P = tractable" or "P means we can write useful programs to solve it", which would make figuring out which problem sets are P a matter of great practical importance, rather than a bit of involved fun.

Too bad Cobham's thesis is obvious rubbish to anyone who doesn't want to make a case for funding their fun.

P means an O(n^C) algorithm for the problem set can be found, where n is the size of the input, and C can be any constant (NP means an answer can be verified with an O(n^C) algorithm, a nondeterministic turing machine essentially being an infinite number of computers checking all possible answers simultaneously). That's any constant. It has been proven that the class P contains problem sets with unboundedly large C.

So you have proven that a problem set belongs (or all problem sets in NP belong) in class P? Bully for you. You still haven't proved there's any algorithm better than O(n^googleplex), and somebody else already proved that you can't just assume there is.

And that's not even getting into how little the Big O characterization of time efficiency tells you (or Big Theta, which I should be using here).

Given the nature of the difference between the definitions of P and NP, I expect that if there is a proof of NP=P by demonstrating the transformation of previously-considered-NP problem sets into P will involve such huge C as to have no practical significance. If they were P with small C, it wouldn't be so hard to figure out that they are P.

Re:P = NP?

[hey!]

I've been in this business since the 1980s. When I started, there were proportionately a lot more math geeks in software than there are today, but by the early 90s there wouldn't have been enough math geeks in all the world to do the work that needed to be done. The people who came into the business had the attitude that complexity and computation theory were just a lot of ivory tower rubbish.

There was a certain validity to this attitude. There was ton of work to be done, but almost all of it amounted to assembling endless variations of the same old kinds applications but in new contexts. It was like snapping together different Lego projects. The mathematically difficult work had already been done for the people engaged in that work, and so their intellectual focus shifted to issues of craft and project management, which were by no means trivial things. Some of us kept algorithm books handy for that odd job where the library routines didn't quite do, but we didn't really need much math. We just needed a rough grasp of O notation and the ability to translate pseudocode into C. Most software guys didn't even go that far. They didn't have *any* math books or references on their shelves, just big, fat tutorial books on vendor provided solutions or architectural philosophy.

Then came the Internet.

A lot of Internet related software falls into the Lego Architecture class, but given a world of data that are interconnected, there's more need than ever for people who can create *new* algorithms that can squeeze gems of value out of that mountain of data quicker than the Universe will perish from heat death. Companies like Google or Facebook or LinkedIn can't just slap a Java front end onto an Oracle database. They have to create new ways to structure and process volumes of data magnitudes beyond anything that existed in the early 1990s.

Fundamental (in the sense of "foundational" rather than "beginner's") CS is once again very practical knowledge to have.

Re:P = NP?

[hey!]

I call BS.

It sounds like you're parroting material from some company's web site. Natural language recognition was an active area of research when I was a student in the early 80s, at which point everyone in the CS department would have been well versed in complexity theory. So far as I know NLP has remained an active field of academic research ever since.

In any case you'd have to assume that PNP (as most of us do), and you'd have to show that *every possible useful natural language recognition application requires processing some large volume of data with some NP-Complete algorithm*. That's a pretty tall order.

Re:P = NP?

[Anonymous Coward]

solvable by a million computers performing a million operations per second in a few hundred years or faster.

Or, you know, since even cheap computers now are capable of performing billions of operations per second, a few weeks.

Also:
1) we're talking about P=NP, not N=NP
2) if you meant P=NP, then you're dead wrong about what it means

Re:P = NP?

[PhilHibbs]

I wrote that because "that's what all the fuss is about". There's more to it, but it's a catchy headline that explains the hype.

Re:P = NP?

[dkleinsc]

It's also worth a cool $1 million if you solve it, thanks to the Clay Mathematics Institute, because it's currently one of the top unsolved problems in all of mathematics as well as being the top unsolved problem in the more specialized computer science world.

And to give you an example of how awesome it would be if P=NP: You could (in theory at least) write a program that took a set of axioms and a hypothesis, and it could tell you reasonably quickly whether the hypothesis was something that could be proven using those set of axioms. Or for architecture and engineering, right now there are programs that can do a lot of the checking of whether a bridge design would collapse, but with this sort of program you could write something that says "design me a bridge that can take a 15-ton load". In short, it would revolutionize what sort of problems computers could solve for us.

However, I should point out that unlike a date, the computer scientists might actually succeed at figuring this one out.

Re:P = NP?

[PPH]

I call BS.

It sounds like you're parroting material from some company's web site.

Nope. An in-house app written at Boeing to translate requirements documents into executable ATE instructions. Every time we'd try to clean up the app by bringing on board some CS people* (thinking that they could optimize data/algorithms and whatnot) they'd just scream about how NLP is not possible. And then we'd go back to running the system, testing airplanes.

*When I left, I had to train my replacement to support, among other things some web apps. The Boeing Computer Services sent over one of their 'wizards' who supposedly knew HTML, Perl, PHP, SQL, etc. So I handed him my documentation notebook and opened a terminal so he could inspect some of the code. After a few minutes of puzzlement, he turned to me and asked, "What language are these written in?". Perl! For christs sake, it says "#! /usr/bin/perl" on the first f*king line!

We had a BCS guy (an old timer, at that) wander by my cubicle and ask for some assistance with a Fortran program he couldn't get to compile. He showed me some notes a co-worker had given him which included a call to some plotting function, lets say "PLOT(....)". The note was written exactly this way, which I and probably every other competent hacker would interpret as "...." means put some parameters there. Go RTFM for PLOT() to figure out what they are. Nope. He had "PLOT(....)" in his source. I could tell you some more stories, but then you'd never get on another airplane.

Re:P = NP?

[hey!]

Well, I didn't say making a successful application performing some restricted set of NLP tasks was BS. It's the notion that a competent "CS person" would claim such an app was impossible because of complexity theory that is BS.

All your anecdote demonstrates is that your group didn't know how to hire computer scientists that were competent -- at least for that job.

Re:P = NP?

[Tyler Durden]

You could (in theory at least) write a program that took a set of axioms and a hypothesis, and it could tell you reasonably quickly whether the hypothesis was something that could be proven using those set of axioms.

No actually, no program can do that.

Re:P = NP?

[Anonymous Coward]

It would basically make almost every hard problem for a computer to solve much faster/easier to solve.

Re:P = NP?

[Anonymous Coward]

You're confusing Cook-Levin with Church-Turing. Church-Turing, which has nothing to do with P and NP, deals with the problem that you describe. According to the Church-Turing thesis, there are some problems that Turing Machines (which includes every computer ever designed) can not solve. Building a computer that could solve the decision problem would be cool, but we have no idea what it would look like (it would require the mathematical equivalent of building a perpetual motion machine--breaking everything we understand in the process).

Cook-Levin, and the P ?= NP problem that they introduced, are about something else entirely. Both P and NP consist entirely of problems that we can solve with a computer. Heck, most of the problems in NP-Complete have very simple solution algorithms. However, for anything in NP, we do not know of an efficient way to solve the problem. Prime factorization is a great example of this (and, incidentally, the reason that IT people should care whether P = NP, since RSA security is only reasonably secure so long as P!=NP).

 

Re:P = NP?

[PPH]

Yeah, yeah, yeah.

We had a saying at Boeing: "Where were you when the paper was blank?"

Re:P = NP?

[bucky0]

Also, in the general case, NLP is hard, but for subsets of the language, with specific vocabulary and grammatical constructs aren't (they're still not trivial, but it's not the same level of difficulty of general NLP).

You just have a language barrier. Being on both sides of the divide (I'm a physicist who started out with, and am still good at CS), there's a number of problems that physicists (or in your case, engineers) have that would map well to things programmers/CS types would know how to solve, but nobody knows how to map the problems to the solutions right.

Re:P = NP?

[adavies42]

the "magic" that's supposed to come out of P=NP is that anything you can describe with a SAT formula can be realized automatically. e.g., if your SAT expresses all the constraints for "a bridge that can take a 15-ton load", the computer can give you a solution to all the free variables in P time.

silly people expect this to scale up to "a play by Shakespeare" or "a symphony by Beethoven"....

Re:P = NP?

[Draek]

And if you give a 10-years-old kid a map and a list of cities, he can give you a decent-ish enough route to take between them in a day as well, but that doesn't prove that the Travelling Salesman problem is in P.

Ask a wrong question, get a wrong answer.

Re:P = NP?

[praxis]

You might not care about this particular problem because it doesn't light your fire, but you do seem to be interested in why it does light the fire of so many other people. Perhaps you could put your sense of intellectual curiosity into finding out what it is about the problem that has so many people interested in it?

Re:P = NP?

[PPH]

You just have a language barrier. Being on both sides of the divide (I'm a physicist who started out with, and am still good at CS), there's a number of problems that physicists (or in your case, engineers) have that would map well to things programmers/CS types would know how to solve, but nobody knows how to map the problems to the solutions right.

That mapping is part of CS (or damned well should be). The analyst sits down with the customer/user/whatever and, through an iterative process, extracts requirements from the user's problem domain and translates them into one of the many s/w methodologies du jour for the developers to work from.

The neat next step would have been to get our NLP system to the point where it could build itself from its own requirements.

This isn't possible

[Anonymous Coward]

10 out of 10 Space Nutters agree, we only have computers because of the Apollo missions. There was no theoretical or practical groundwork done prior to large rockets.

Determinism

[Lynal]

P=NP. The easy way to understand NP (non-deterministic polynomial time) are problems that can be solved with age old the guess and check method. P=NP roughly implies that any problem that can be solved with guess and check can also be solved deterministically.

What has happened since then

[JoshuaZ]

So, what's happened since then? We're still a long way from resolving P ?= NP. There's been a lot of success showing some techniques won't work. The fact that P^A != NP^A for some oracle A and P^B = NP^B for some other oracle B shows that a lot of possible paths simply won't work. Thus for example, there can't be any clever but essentially straightforward reduction of NP problems to P because then we would have P^A=NP^A for all oracles. Similar remarks apply to the so-called natural proof barrier.

There's been more success with related problems. In the last few years, the apparent size of P has grown. Thus, Agrawal et. al. showed that primality testing is in P http://en.wikipedia.org/wiki/AKS_algorithm and there's been a lot of success with taking randomized algorithms that lie in BPP and producing non-randomized versions that are in P. This had lead many to suspect that in fact P=BPP. Most recently there's been some very good work with circuit bounds. Ryan Williams has done very recent technical work showing that NEXP and ACC are not equal. This work seems to get around the natural proof barriers. There's also been some work relating complexity questions to algebraic geometry and the permanent of a matrix. ( No, that's not a typo- http://en.wikipedia.org/wiki/Permanent ). So there's a lot of interesting work going on, but it seems that we're pretty far from actually resolving whether P != NP. I suspect that we'll prove the weaker result that P != PSPACE before we resolve the stronger claim that P != NP.

Re:What has happened since then

[Anonymous Coward]

While I applaud your effort to scientifically enlighten the /. crowds, I would like to share something that is easier to understand by the average /. user:

Finding Osama to kill him is not a P problem because it can't be done quickly in polynomial time.
Verifying that Osama is dead once you have his body is an NP problem because it can be done quickly in polynomial time. ("He's dead, Jim.")
If all NP problems were also P problems (P=NP), Osama would have been found, killed and verified to be dead before the end of September 2001, but it took almost 10 years for him to be found and killed, so it's obvious that P != NP.

There, Osama proved this silly theory wrong once and for all. Q.E.D. (And don't try to make this look like I wanted all-Q.E.D. to sound like a certain organization that Osama liked.)

Re:What has happened since then

[xyourfacekillerx]

I don't know if that analogy works. Verifying he is dead, and finding him, aren't accomplished upon the same model of abstract computation mechanism. Verifying a subset of a set has a certain sum, and finding a subset within a set that has that sum, those are problems that would use the same means of computation and information processing, albeit different algorithms. Besides, the fact that P = NP doesn't mean one automatically, inherently can find the correct algorithm to go ahead and compute the answer. it may take me a long time just to freakin find the algorithm. Then, once the algorithm is executed, we'd find that computation is in polynomial time. In other words, the "problem" of P = NP doesn't assume that the method used to verify an answer is identical to the method used to compute the answer, and it doesn't assume we'd be able to get the algorithm for the latter; it would just assume that, if P = NP, we know there IS such an algorithm out there... finding it is something else altogether.

Well that's how I've been regarding the issue for years now, and a lot of my work would suffer greatly if I had such a fundamental misunderstanding here...

btw, I am holding out that P = NP.

Re:What has happened since then

[Tyler Durden]

This is easily the best post on the topic I've seen so far here. Have to read through it a few more times to understand it all, honestly.

I remember hearing about the AKS algorithm back when I was a grad student. Amazing stuff.

Re:What has happened since then

[Anonymous Coward]

Thanks for the post, that was incredibly insightful. I've been studying the history of complexity theory and P ?= NP question recently, but I haven't found any good sources summing up the more recent (post -92 or thereabouts) results in the field. Are there any citable publications (books, articles, whatever) you could recommend on the subject?

Re:What has happened since then

[JoshuaZ]

It isn't my area specifically so I may not be the best person to give advice, but Scott Aaronson's blog - http://www.scottaaronson.com/blog/ seems to be a good way of keeping up on a lot of these issues.

Bachelor Arms

[Anonymous Coward]

Huh. I drove by there any number of times while I lived in Cleveland. I had no idea that place was where the conference took place. Instead of a motel, I think it's now a real-world Bachelor Arms, complete with long-term stay efficiencies and rent discounts.

Four Dead In O-HI-O

[phorest]

Wow so close to history TWICE that day.
Since I was only ten years old at the time I remember the the shootings but not this bit o' history. I did live around that area, I do know that hotel did turn really sleazy just a few years after that symposium.

Coincidence?...

Re:Four Dead In O-HI-O

[blair1q]

Probably. It's NP-hard out there for a pimp.

Just finished a final exam on Theory of Automata

[Missing.Matter]

There was a question, in a round about and not obvious way, asked us to prove P = NP. Dirtiest most evil trick question I've ever encountered.

Re:P=NP

[spottedkangaroo]

NP-hard is different than NP-complete.

Re:Just finished a final exam on Theory of Automat

[betterunixthanunix]

When I took a graduate level compilers course, the professor gave a quiz early in the semester on writing CFGs. One of the questions was essentially to write a CFG for this language:

a^n b^n c^n

Quite a few people had trouble finding the right answer...

Wow Slashdot has gone downhill...

[DNS-and-BIND]

I looked in to this discussion just because I wanted to see what the hardcore science/math nerds were saying, and instead I get a dozen posts asking, "What the hell is P=NP, LOL." Time was, you could look into math threads on Slashdot and see graduate students talking shop. Even if I didn't understand half of what they said, it was still enlightening.

Re:Wow Slashdot has gone downhill...

[Abstrackt]

Back when I started reading Slashdot (1999), being a "nerd" meant that science/math and "zomg computers are magic!" were your life so it made sense that the articles catered that crowd. Nowadays, being a "nerd" has come to mean so many different things, most of them not as nerdy as us old guys remember when we had to punch cards uphill both ways so it makes sense that this site would change accordingly.

Re:Wow Slashdot has gone downhill...

[Anonymous Coward]

10 years ago, Slashdot's typical reader was a 25-35 year old US college grad with a tech degree. Now the typical /. reader is an EU 15-20 year old.

Re:Wow Slashdot has gone downhill...

[slyborg]

That was probably back when the US had graduate students in math and science. They're off discussing CDOs and other advanced variations on the old shell game now.

Re:Wow Slashdot has gone downhill...

[Anonymous Coward]

Bah, PhD only means not good enough for a Nobel prize. As dumb as you are, they are even dumber, and they don't even know it. Now, instead of posting here, they write papers wherein any drop-out could poke holes easily.
They use all that jargon to keep people from seeing just how flawed their theories are.

Re:Wow Slashdot has gone downhill...

[Anonymous Coward]

Does it mean anything to be European? :)

Re:Wow Slashdot has gone downhill...

[AkkarAnadyr]

Yeah. Americans 15-20 years old generally can't read, barring lolspeak.

Re:Wow Slashdot has gone downhill...

[Anonymous Coward]

"It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$ 1,000,000 prize for the first correct solution."

As per http://en.wikipedia.org/wiki/P_versus_NP_problem

Little more to this than just talking shop, the almighty unbacked deity called The Dollar is at work here. Not to mention, tis the season for finals.

Re:Wow Slashdot has gone downhill...

[dominious]

"What the hell is P=NP, LOL."

maybe LOL = OL^2 but im not sure what O and L stand for in this context...

Re:Wow Slashdot has gone downhill...

[koreaman]

Are you an idiot? The U.S. dominates every other country in the world for math research output (which is closely correlated to the number and quality of Ph.D students), and I assume the same is true in most of the sciences.

Re:Wow Slashdot has gone downhill...

[Anonymous Coward]

Adding to that, could anyone recommend a site like that? Slashdot is awful nowadays, but due to bad habit I keep coming back every other day.

Re:Wow Slashdot has gone downhill...

[Anonymous Coward]

Show 'em. The dozen posts.

Re:Wow Slashdot has gone downhill...

[Anonymous Coward]

Speaking as one of the math nerds, we aren't speaking up much because there's not much to say. Basically, we had a question posed, then nobody was able to answer it. Fast-forward 40 years and... we still don't know.

There's not much exciting you can say about "I dunno".

Re:Wow Slashdot has gone downhill...

[Five Bucks!]

Where have all the nerds gone?

I used to love /. with the esoteric news clippings that you'd never find in the mainstream. Now the front page is full of Sony hatred and absurd news bites proclaiming the end of X...

Re:Wow Slashdot has gone downhill...

[Anonymous Coward]

LOL = OL^2 only if the group is Abelian.

Re:Wow Slashdot has gone downhill...

[Arterion]

Yes, but not from U.S. graduate students. From foreign graduate students studying in the U.S.

Re:Wow Slashdot has gone downhill...

[Anonymous Coward]

It's time for a Superslashdot.

terror savings; each citizen gets 1 million $$$$

[Anonymous Coward]

before it's all gone already? the americannex dream is finally realized. plus, not only completely reviving our god blessed economy, each citizen can now afford enough weaponry & personal spy stuff so that atmospheric & other atmostfearinc terrorism will continue to be our #1 chosen businesses. & now recreation (or continued decreation) for centuries to come. it's not just a dream after all.

after all, we've all paid in with big parts of our lives, so far. after disarming, there'll be lots of extra fake dough everywhere right away. if we had prayers, this would be it?

Re:Just finished a final exam on Theory of Automat

[Missing.Matter]

Did it turn out to be a trick question or did he really want a^nb^n? The former is very evil while the latter I guess I can understand.

It's only 845 on the west coast...

[Anonymous Coward]

The graduate students are still asleep :)

Re:Just finished a final exam on Theory of Automat

[betterunixthanunix]

It was a trick question meant to test how many people were paying attention in their theoretical CS courses.

Sadly the difference is more like ...

[Nicolas MONNET]

This is a real world example I've seen a dozen times. Given a spec that requires a parser, the CS type will come up with a complicated (to outsiders) solution that few people can understand but works perfectly. The IT type will not recognize that it is a parser, does not know what a parser is, and will implement a very buggy "solution" with regexps (cf. the MySpace XSS fiasco from a few years back).

Oh who am I kidding; there is no such thing as a spec. I've never seen an actual one in the enterprise.

I always wanted to go to that Stouffers.

[Anonymous Coward]

No, not because i understand the P NP problem and am a fan. Just because i live relatively close to that
Stouffers.

K

Re:P=NP

[Anonymous Coward]

NP-Complete is the intersection of NP and NP-Hard.

It's Stephen Cook, not Steven.

[roman_mir]

What the hell? It was Stephen Cook when I took his classes back in the nineties.

Hey, /. editors, how is that guy, what's his name, Commander TacoBell doing?

Re:P=NP

[kasperd]

NP-complete is by definition the intersection between NP and NP-hard. There are for sure NP-hard problems, which are not in NP, so you are right that the sets are not identical. I believe the halting problem is NP-hard, but it certainly isn't NP-complete.

Tautology is hard?

[Anonymous Coward]

Now that's a tautology

Slacking off from my complexity class right now...

[Anonymous Coward]

(I'm a grad student in CS who should be writing a summary on Toda's theorem right now, and instead am looking at slashdot. God dammit.)

An intuitive way to look at NP problems is that you're asking whether a solution exists to some other problem that's easy to verify. It's easy to look at a boolean formula of ones and zeroes, joined by ands, ors, and nots, and tell whether it comes out to true. It's very hard, however, to replace the ones and zeroes with variables, and tell whether any assignment of those variables to ones and zeros will result in a formula that comes out true.

The analogy of songwriting is illustrative. I can tell if a song is good or bad pretty easily. But that doesn't mean I can write a good song. Where do I start? To write the song, I have to choose from all the different notes, then choose another note out of all the possible notes, and so on. Once I've come up with a song, I can sit back and judge its quality (relatively) easily.

Now, one solution is to generate all possible songs, and when I hit upon one that's good, record it and become a rock start. But generating all possible songs, then judging them, takes a very long time. (And if I add a new instrument to the mix, it will at least double the amount of work I have to do, if I'm generating all songs.)

But a theoretical NP machine generates "songs" as fast as it can judge "songs". (We're not really talking about songs, we're talking about satisfying assignments to boolean formulas.)

Many AI problems are NP-complete, which is why AI classes are all about heuristics. So if anyone ever comes up with P = NP, find John Connor.

Source linked

[Anonymous Coward]

http://blog.computationalcomplexity.org/2011/05/forty-years-of-p-v-np.html

It seems we've made tremendous advances in plagiarism though.

Oh I have wasted my life!

[Anonymous Coward]

says P=NP guy.

Re:Just finished a final exam on Theory of Automat

[aepurniet]

the notation itself is ambiguous, but i suppose you could do it (what we would consider) wrong, and define the ^ operator to only take one token.

Proof

[Hugundous]

I've found a very nice solution to this problem. Unfortunately this comment box is too small to contain it.

Re:Proof

[EnsilZah]

The lower right corner allows you to extend it, dude.

How hard did it seem?

[neilmoore67]

I was at a talk by Stephen Cook once and he actually set proving P != NP or P = NP as an undergrad student project. Shows people then didn't fully appreciate how difficult it was. Perhaps he spent a week trying to solve it and felt close enough to be sure it could be done.

Re:P=NP

[spottedkangaroo]

Surely, but he was using the terms interchangeably. They're really not. Entirely different kind of proofs. Similar, but weaker.

Source

[Anonymous Coward]

This was ripped from the following original source:
http://blog.computationalcomplexity.org/2011/05/forty-years-of-p-v-np.html

Re:P=NP

[dkf]

I believe the halting problem is NP-hard

No. The halting problem is wholly insoluble since if a solution existed, we could trivially construct code that only halted if it didn't halt and vice versa: a complete contradiction in terms. NP-hard problems can all be solved with sufficient application of computing power; you might have to wait a long time, but they are still properly algorithmic. (The "P=NP?" question is about whether efficient algorithms exist for solving a very large class of problems, or whether they just have to be brute-forced.)

Happiness is a click away.

[ed1park]

Computer Science: An Overview by Brookshear

http://www.amazon.com/gp/product/0132569035/ref=pd_lpo_k2_dp_sr_1?pf_rd_p=486539851&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0201781301&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=156PMT03KVNBZ06TDF4D

Get it, and you can thank me later.

Hazards of P=NP

[mpaque]

I'm pretty sure that if you prove P=NP, that there may be consequences. It you are very, very lucky, Bob from the Laundry will pop by and arrange for a new career for you, or at least keep your brain from being eaten.

If you're not so lucky, well, pointing a loaded theorem at the ... things ... that cast shadows on the walls of Plato's cave may make them pay attention. This is, however, a dangerous process, because many of the shadow-casters are unclear on the distinction between pay attention and free lunch buffet here. [1]

1. http://en.wikipedia.org/wiki/Charles_Stross#The_.22Bob_Howard_.E2.80.94_Laundry.22_series

Re:P=NP

[kasperd]

NP-hard problems can all be solved with sufficient application of computing power

There is no requirement for the problem to have a solution. Even if there is no way to test if an input is in a set L, it may still be the case that L is hard. In order for L to be NP-hard, there has to be a polynomial time algorithm that can reduce any NP problem to L. If you take L to be the halting question, then such a reduction is trivial. Just simulate the nondeterministic TM with all possible choices for the nondeterministic parts until you find the one that makes it halt and accept. If no such choices exist, the simulation will run for ever. Hence, it will halt iff the input for the reduction was in the NP set that we were interested in.