# Forty Years of P=NP?

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

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

## 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)

## Re:P=NP is a waste of time. (1)

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

## 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)

## 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)

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)

## 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)

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)

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)

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)

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)

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)

## 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)

## 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)

## Re:P=PN (1)

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

## 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)

## 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)

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)

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

## Ambitwistor (1041236) | more than 3 years ago | (#36024136)

P vs. NP for dummies [scottaaronson.com]

## 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)

## 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)

## 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)

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

http://science.slashdot.org/story/10/08/08/226227/Claimed-Proof-That-P--NP [slashdot.org]

http://science.slashdot.org/story/11/01/20/1546206/Polynomial-Time-Code-For-3-SAT-Released-PNP [slashdot.org]

http://science.slashdot.org/story/11/02/28/149244/No-P--NP-Proof-After-All?from=rss [slashdot.org]

http://science.slashdot.org/story/10/08/11/0239209/Possible-Issues-With-the-P--NP-Proof [slashdot.org]

http://science.slashdot.org/story/10/09/10/1847245/How-the-Web-Rallied-To-Review-the-P--NP-Claim [slashdot.org]

Can anyone explain what all the fuss is about ?

## 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)

## 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)

## 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)

## 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)

## Re:P = NP? (2)

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

## 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)

## Re:P = NP? (1)

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

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)

## Re:P = NP? (1)

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

## Re:P = NP? (1)

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

## 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)

## 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)

## 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)

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

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

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)

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

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

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

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

## 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)

## 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?