Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Forty Years of P=NP?

CmdrTaco posted more than 3 years ago | from the turns-out-they-both-equal-seven dept.

Math 222

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."

cancel ×

222 comments

P=NP is a waste of time. (-1)

Anonymous Coward | more than 3 years ago | (#36023980)

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. (0)

Anonymous Coward | more than 3 years ago | (#36024052)

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. (1)

martas (1439879) | more than 3 years ago | (#36024474)

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

Actual origins are even earlier (2, Informative)

Anonymous Coward | more than 3 years ago | (#36023988)

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 (2, Interesting)

jjohn (2991) | more than 3 years ago | (#36024004)

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

Sad, sad old hacker.

Re:P=PN (1, Insightful)

war4peace (1628283) | more than 3 years ago | (#36024078)

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

Re:P=PN (0)

Anonymous Coward | more than 3 years ago | (#36024142)

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 (5, Informative)

Yold (473518) | more than 3 years ago | (#36024218)

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 (1)

blair1q (305137) | more than 3 years ago | (#36024466)

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 (0)

Anonymous Coward | more than 3 years ago | (#36024480)

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

Re:P=PN (2, Informative)

Anonymous Coward | more than 3 years ago | (#36024604)

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=NP (1)

spottedkangaroo (451692) | more than 3 years ago | (#36024486)

NP-hard is different than NP-complete.

Re:P=PN (2, Informative)

Anonymous Coward | more than 3 years ago | (#36024570)

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 (0)

Anonymous Coward | more than 3 years ago | (#36024880)

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 (4, Informative)

razberry636 (601469) | more than 3 years ago | (#36024644)

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 (4, Informative)

Missing.Matter (1845576) | more than 3 years ago | (#36024694)

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 (1)

Missing.Matter (1845576) | more than 3 years ago | (#36024796)

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 (1)

ObsessiveMathsFreak (773371) | more than 3 years ago | (#36024854)

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 (1)

mog007 (677810) | more than 3 years ago | (#36025082)

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

Re:P=PN (2)

Kamiza Ikioi (893310) | more than 3 years ago | (#36025186)

Sounds right to me. It's most well known as the Knapsack Problem [wikipedia.org] . 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 (3, Informative)

betterunixthanunix (980855) | more than 3 years ago | (#36024100)

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 (1)

FrootLoops (1817694) | more than 3 years ago | (#36024704)

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 (3, Informative)

betterunixthanunix (980855) | more than 3 years ago | (#36024842)

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 (1)

Nicolas MONNET (4727) | more than 3 years ago | (#36025234)

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 (2)

Missing.Matter (1845576) | more than 3 years ago | (#36024994)

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 (1)

bunratty (545641) | more than 3 years ago | (#36024164)

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 (1)

vlm (69642) | more than 3 years ago | (#36024312)

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 (1)

bunratty (545641) | more than 3 years ago | (#36024526)

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 (1)

Missing.Matter (1845576) | more than 3 years ago | (#36024550)

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 (1)

FrootLoops (1817694) | more than 3 years ago | (#36025052)

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 [wikipedia.org] 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 (1)

FrootLoops (1817694) | more than 3 years ago | (#36024560)

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 (1)

Missing.Matter (1845576) | more than 3 years ago | (#36025154)

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 (0)

Anonymous Coward | more than 3 years ago | (#36024608)

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 (0)

Anonymous Coward | more than 3 years ago | (#36024726)

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 (1)

Yvanhoe (564877) | more than 3 years ago | (#36024906)

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 (0)

Anonymous Coward | more than 3 years ago | (#36025214)

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

So? (-1, Redundant)

CTU (1844100) | more than 3 years ago | (#36024014)

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? (1)

sakdoctor (1087155) | more than 3 years ago | (#36024108)

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

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

Re:So? (1)

ThePangolino (1756190) | more than 3 years ago | (#36024574)

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

Re:So? (0)

gnick (1211984) | more than 3 years ago | (#36024114)

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? (1)

doshell (757915) | more than 3 years ago | (#36024150)

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

Re:So? (1)

gnick (1211984) | more than 3 years ago | (#36025042)

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? (0)

Anonymous Coward | more than 3 years ago | (#36025108)

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? (0)

Anonymous Coward | more than 3 years ago | (#36024228)

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

Re:So? (1)

vlm (69642) | more than 3 years ago | (#36024116)

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 [wikipedia.org]

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

Re:So? (1)

Anonymous Coward | more than 3 years ago | (#36024158)

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? (1)

JoshuaZ (1134087) | more than 3 years ago | (#36024264)

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? (1)

betterunixthanunix (980855) | more than 3 years ago | (#36024376)

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? (0)

Anonymous Coward | more than 3 years ago | (#36024542)

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? (1)

vlm (69642) | more than 3 years ago | (#36024490)

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? (1)

betterunixthanunix (980855) | more than 3 years ago | (#36024602)

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? (0)

Anonymous Coward | more than 3 years ago | (#36024186)

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? (0)

Anonymous Coward | more than 3 years ago | (#36024488)

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)

non-droids in deeper water than ever? (0)

Anonymous Coward | more than 3 years ago | (#36024038)

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.

And the corollary... (1)

errxn (108621) | more than 3 years ago | (#36024068)

YP != MP

Re:And the corollary... (1)

MadKeithV (102058) | more than 3 years ago | (#36024324)

Hah, MP > YP.

If you just paste and copy (0)

Anonymous Coward | more than 3 years ago | (#36024084)

then add at least a pointer to the source. [computatio...lexity.org]

P = NP? (1)

Yuioup (452151) | more than 3 years ago | (#36024104)

Re:P = NP? (4, Insightful)

vlm (69642) | more than 3 years ago | (#36024174)

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? (1)

PPH (736903) | more than 3 years ago | (#36024338)

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? (2)

vlm (69642) | more than 3 years ago | (#36024662)

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? (0)

Anonymous Coward | more than 3 years ago | (#36024734)

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

Re:P = NP? (1)

steelfood (895457) | more than 3 years ago | (#36024660)

"date with a girl" moment.

And prostitution doesn't count.

Re:P = NP? (1)

PhilHibbs (4537) | more than 3 years ago | (#36024226)

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

Re:P = NP? (1)

betterunixthanunix (980855) | more than 3 years ago | (#36024270)

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

Re:P = NP? (1)

Tyler Durden (136036) | more than 3 years ago | (#36024452)

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? (1)

betterunixthanunix (980855) | more than 3 years ago | (#36024484)

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

Re:P = NP? (2)

betterunixthanunix (980855) | more than 3 years ago | (#36024238)

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? (0)

Anonymous Coward | more than 3 years ago | (#36024612)

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? (1)

betterunixthanunix (980855) | more than 3 years ago | (#36024630)

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

Re:P = NP? (1)

Tyler Durden (136036) | more than 3 years ago | (#36024252)

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? (1)

bigstrat2003 (1058574) | more than 3 years ago | (#36024476)

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? (1)

betterunixthanunix (980855) | more than 3 years ago | (#36024696)

"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? (1)

bigstrat2003 (1058574) | more than 3 years ago | (#36024792)

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? (0)

Anonymous Coward | more than 3 years ago | (#36024940)

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? (1)

maxume (22995) | more than 3 years ago | (#36024834)

So maybe he is a plumber or designs airplanes.

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

Re:P = NP? (0)

Anonymous Coward | more than 3 years ago | (#36024714)

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

Re:P = NP? (1)

martas (1439879) | more than 3 years ago | (#36024552)

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 [wikipedia.org] .

Re:P = NP? (0)

Anonymous Coward | more than 3 years ago | (#36024624)

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? (1)

stoicfaux (466273) | more than 3 years ago | (#36024706)

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.

This isn't possible (0)

Anonymous Coward | more than 3 years ago | (#36024140)

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 (1)

Lynal (976271) | more than 3 years ago | (#36024146)

P=NP [wikipedia.org] . 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 (3, Informative)

JoshuaZ (1134087) | more than 3 years ago | (#36024180)

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 [wikipedia.org] 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 [wikipedia.org] ). 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 (0)

Anonymous Coward | more than 3 years ago | (#36024572)

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 (1)

xyourfacekillerx (939258) | more than 3 years ago | (#36024886)

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.

Bachelor Arms (0)

Anonymous Coward | more than 3 years ago | (#36024318)

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 (1)

phorest (877315) | more than 3 years ago | (#36024366)

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 (1)

blair1q (305137) | more than 3 years ago | (#36024506)

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

Just finished a final exam on Theory of Automata (2)

Missing.Matter (1845576) | more than 3 years ago | (#36024472)

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:Just finished a final exam on Theory of Automat (2)

betterunixthanunix (980855) | more than 3 years ago | (#36024530)

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...

Re:Just finished a final exam on Theory of Automat (1)

Missing.Matter (1845576) | more than 3 years ago | (#36024746)

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.

Re:Just finished a final exam on Theory of Automat (2)

betterunixthanunix (980855) | more than 3 years ago | (#36024872)

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

Wow Slashdot has gone downhill... (4, Interesting)

DNS-and-BIND (461968) | more than 3 years ago | (#36024532)

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.

It's only 845 on the west coast... (1)

Anonymous Coward | more than 3 years ago | (#36024858)

The graduate students are still asleep :)

Re:Wow Slashdot has gone downhill... (2)

Abstrackt (609015) | more than 3 years ago | (#36025014)

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... (1)

Anonymous Coward | more than 3 years ago | (#36025080)

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... (1)

slyborg (524607) | more than 3 years ago | (#36025226)

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... (0)

Anonymous Coward | more than 3 years ago | (#36025236)

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.

terror savings; each citizen gets 1 million $$$$ (0)

Anonymous Coward | more than 3 years ago | (#36024544)

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?

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...