Slashdot Mirror
Consequences of a Solution to NP Complete Problems?
m00nshyn3 asks: "If a person were to find a O(n) solution to an NP complete
problem, it would obviously be a great advance in computer science,
but what are the consequences of such a discovery? Would our most
popular implementations
of cryptography be useless overnight? It seems like there is a lot
of immediate damage that could occur if such a solution were found.
So if (when) the time comes, what is the responsible way for the
solution to be made public?" If you had such an algorithm in hand,
what could you do with it? It would be interesting to see how many
problems we could map into the NP Complete model.
Salesmen will certainly be happy when such an algorithm is found. For other classes of NP-complete problems, check this book.
Analogously, if it was learned that eating Hostess Twinkies that had been marinated in thai green curry sauce while bathing gave one super-strength and x-ray vision, we would have to become gravely concerned about the possible rise of Thai-Twinkie-powered super-criminals who know what we look like in our Underoos. This is clearly something that man was not meant to know. Won't someone think of the children?
Apart from rendering most asymmetrical encryption useless, what benefit would it be to computer science? Seems like one of those rather useless things like "calculating the nth digit of pi using a cluster of 40,000,000 PCs".
Really I don't know and am curious (and maybe it'll let us have compression that will compress down to one byte! :-) See the prior story about the "data teleporter" to understand that joke).
First off, if they found an O(n) algorithm, that means that all NP problems would be in linear time. I'm assuming the poster means O(n^t) where t is independent of n.
now if that were the case, i'd use it to build nifty AI's. Most ai problems are NP complete since they involve non-deterministically searching a problem space. Stuff like crossword puzzles and route planning come to mind for this one. Most of these problems do map to SAT, so it would be very short time before we start seeing some really intelligent AIs for a lot of your typical tasks.
"To save the planet, I had to go to the worst spot on Earth, and that was Philadelphia." -- Sun Ra
If we knew the answer to that, we'd already have the solution!
And shouldn't this be under Ask Slashdot?
___
The way to see by faith is to shut the eye of reason. --Ben Franklin
Publish it as soon as possible, get credit for it, and rack up the monetary prize, don't you think?
No we wouldn't see the whole crypto world come smashing down around us, but a large portion of it. All of the Public Key crypto would be reduced from an assumed set of hard problems to a set of simple ones. No more digital signatures, or communications without pre shared secrets. Although any system using just symmetric ciphers would be immune from this reduction in work effort.
Even if a timly NP complete solution is not found, PK based on factoring or discrete logarithms might get broken by other discoveries. For that reason I'm always watching the emergence of new PK systems such as FAPKC and some of the lattice based codes.
-- The_Messenger
I'd release it to the public, then sit down until they hand me my well-deserved Turing award.
Seriously, there are more advantages (quick solutions to complex problems, like the traveller salesman) than disadvantages (cracking easily certain encryption mechanisms) to this.
But then again, my gut feeling is that P!=NP.
"Trust me - I know what I'm doing."
- Sledge Hammer
The solution will never be made public. It will be abducted and dissapeared away into the NSA or worse.
Start Running Better Polls
on who found the solution. Depending on the culture and the individual the proper thing maybe posting it to slashdot. If someone in the NSA finds the solution (if it exists) the 'proper' thing maybe to hide it forever.
Most likely it will be a 1st world academic who will find a solution, in which case I think the common course would be to claim the find, and open it for peer review after doing a thorough personal review. Humans, academics in particular, are very egocentric creatures.
If someone could find a way to turn mercury into gold, [blah blah]
If a person could find an function f(x) that returns the xth prime number, [blah blah]
If only it was easy to find any decimal of PI with a simple formula, [blah blah]
If only I could make up a nice AskSlashdot to get my story posted, [blah blah]
"A door is what a dog is perpetually on the wrong side of" - Ogden Nash
I'd go to the government with it first. Something like this would definitely be of interest to Nat'l security
Crypto algorithms are strong for other reasons. Factoring primes is not a difficult problem... the fastest known solution is already O(n), the reason it's time consuming is that you can choose arbitrarily large values of n, in which case, you need to do better than O(n) in order to effectively break it. One time pads are another thing altogether. There is no algorithm of any order that can break a proper OTP (note that an improper OTP, i.e. one who's pad is not truly random or who pad is reused could be cracked). Other algorithms are based on other principles, but in any case, most are based on mathematically difficult or impossible problems, not computationally difficult ones.
I like to play children's songs in minor keys.
"We're all sons of bitches now." --J. Robert Oppenheimer
Whoever made the discovery would have to notify Verisign, RSA, the government, and major corporations in secret at least a few weeks before the discovery became public knowledge. If they didn't, the economic hit from loss of privacy would be overwhelmingly staggering. So if we ever see lots of major corporations taking their encrypted systems off of the Internet, then we have an idea of what happened.
The problem is that if somebody solves one NP-complete problem, they've all been solved, since they're all reduceable to each other in P time, so no cryptographic system would be safe.
And, of course, the mathemetician would probably be sued by the RIAA for violating the DMCA.
And then ask why it already is
Considering that the Travelling Salesman Problem is NP complete and affects almost any problem that involves delivering something to several destinations in an optimal fashion. A solution to NP problems ould have widespread ramifications in improving many aspects of businesses that involve deliveries (including the airline business now that I think about it).
Or we could make it a lot easier on ourselves and just break into someone's house to get their password instead of having to go through a bunch of math and all that just to have the rights to say, '0wns j00'.
Job? I don't have time to get a job! Who will sit around and bitch about being broke and unemployed then?
This is not a flame or a troll, I'm serious.
Ask Slashdot is normally not-so-bright, but this one is waaaay up there for stupid questions. How does this stuff get through, then to the front page, no less?
...and work no more. ;-)
There is a real danger somebody will do this.
be the king of MineSweeper
delete free(system.gc);
Even if someone manages to prove that P=NP, it doesn't mean that a reasonably efficient solution can be found. All it means is that an NP-complete problem can be solved in polynomial time. That polynomial can still be huge, say N^1000. Except for really large N, current exponential-time algorithms could be superior to polynomial-time ones.
So, the short answer is that proving P=NP probably won't ruin your encryption. On the other hand, if someone did prove it, there will probably be a mad scramble to invent some new encryption schemes, just in case.
-Chris
Look, buddy. Some of us happen to like Oasis.
If you solve an NP complete problem in O(n^65535) time, you have just shown that P == NP. However, you still wouldn't be able to crack any of the NP complete problems that cryptography is based on in a reasonable amount of time.
;)
Because trust me, if it was a low exponent for x, we'd have found it already.
Besides, they'd just move to problems that are not NP complete for the popular cryptography algorythims. Cryptographers are too smart for their own good, you know.
Gentoo Sucks
Patent it and sue the ass off anybody who tries to use it. :-)
...laura
Seriously, a problem is NP-complete if anwers can be verified quickly. I guess we will have to use cryptography algorithms asking such things as 'What is the meaning of life, to be or not to be, where we came from', etc...
And no, 42 should not be used since it's already known
Buy a Nintendo DS Lite
The interesting question is not:
:-)
/. community does not care about that difference.
... so I have no clue if it affects public key encryption, via eliptic curves or prime numbers. However, where I can imagine that it might be affecting eliptic curve encryptions, I doubt advances in that field migh thave any benefit in factorizing of prime numbers.
<i>
If a person were to find a O(n) solution to an
NP complete problem
</i>
The interesting question is:
<I>to find a O(<x>) solution to an NP complete problem
</I>
Where <x> is any polynom of the kind n, n*n, n+n*n, n*n*n, and so on.
I'm quite sure neither the asker of the question nor the poster understands the difference between P, NP and NP complete
And I'm realy more sure that the general
I *know* the difference, but I learned it only for passing a test
Regards,
angel'o'sphere
Cost free eBook I read (by iBook/Kobo/Amazon/ObookO/Gutenberg etc.): "The Green Odyssey" by Philip Jose Farmer.
I have no idea if this is on topic, but it was an intersting read of some people's understanding of NP during a CS 105 class that talked about NP probalems.
5 /2 000S/Questions/question.42.html
http://www.math.grin.edu/~rebelsky/Courses/CS10
First of all, it doesn't even have to be a O(n) solution. NP hard problems are exponential, so even a O(n^2) or n^3 or anything polynomial would be a major breakthrough.
As to the outcomes...
Personally, I've though about this a lot in my algorithms class. The way the theory goes, if you can solve an NP complete problem in polynomial time then it means that all the other problems in NP complete are part of P (or something to that effect). Where I see the problem is that all encryption EVERYWHERE is based on the face the a very large number can't be easily factored into it's two primes. This is designated as an NP hard problem. So, cracking encryption in polynomial time would be possible.
This is when I get a large government grant and construct the worlds most secure underground bunker. Then I release the the solution to the world and hide. The consequences would be chaotic. Nothing would be digitally secure anymore, anywhere.
But, the chances that someone will actually solve an NP problem is slim... But hey, It could happen
Please take an algorithms course. It's taught in any university with a decent CS faculty. And if you think the course is too hard for you, feel free to come back and ask slashdot again. (Other questions may include: "what's a Turing Machine?" and "can you run Linux on it?")
As an aside, when did slashdot become a meta-search engine? Oh wait... never mind!
___
If you think big enough, you'll never have to do it.
Would our most popular implementations of cryptography be useless overnight?
All of our cryptography schemes are made useless more often sooner than later.
Which is why I think this government initiative to install viruses on our computers is not only a bad idea, but an awful waste of money, that could be put into better use. Like an extra daisy-cutter or something.
I am not sure that quantum computation can solve an arbitrary NP problem in O(n) time, but if I understand it correctly you still get the effect of non-deterministic search in a space limited by the number of particles in coherent quantum state. As the article points out the incentives to develop even something close P time solution of NP are huge. So the race to build a reliable and scalable quantum computer is on.
Is 42. ;)
-- Dan
Regardless of what was said above, this doesn't destroy public key cryptography at all. The two biggest mathematical assumptions used in PK crypto are that:
:)
a) Factoring large numbers is hard
b) Solving discrete log problems is hard
Mind you, these are *not* NP-Complete problems (at the moment). They are believe to be in NP, but that's another story completly. Finding a polynomial algo for an NP-complete problem does not give you an algo for factoring and/or solving DLP problems.
Now on the other hand, if you had a quantum computer, you could factor in quadratic time, and solve DLPs in cubic time. Now *that* would be somewhat bad.
If somebody found a solution to an NP complete problem, it would open the doors to a whole new world of algorithm efficiency. That's a small statement compared to how much easier it would make you computer science degree program.
I've actually got quite a few pizza this way. If this NP solution helps to speed up pizza delivery, I don't I would like that, at all.
Secondly, there are very few encryption problems that are NP-complete. Now NP is a general class of problems that don't have a O(n^k) solution, but that's different than NP-complete. (I wouldn't want to use a NP-complete encryption anyway, given how much effort seems to be going into that area!) In fact, most encryption is based on the infeasibility of calculating discrete logs in Z mod n. However, this problem is very close to being solved itself. I haven't read up too much on what's going on there, but apparently they've been mapping Z/n to elliptic curves (don't ask me how).
Consequences of that? Well, for starters, if you can calculate a discrete log in Z/n, then it's relatively trivial to recover some multiple of the order of the order of the group - which makes primality testing easier (your order will be k*(n-1)). However, this means you should stick with elliptic curve-based encryption for now, as the NSA probably has discrete log cracked :-P
Not publish your solution, go to the people in the know and use the knowledge to your advantage. Secretly rip of banks all over the world, bring down governments, get yourself in a position of power. The possibilities are endless.
There is also a chance that an agency such as the NSA or the British intelligence services have ALREADY found a solution. Just look at rsa, or how long the Brits kept enigma and their digital computers secret (predating ENIAC). Without a credible alternative to RSA at the moment it would be sensible for such an organisation to keep a solution secret.
Or have I just been watching too many spy films?
The qustion should be: prove that there is no such algorithm. But because that prove does not exist yet, you can also give a counter prove by finding one.
Instinctivly you could say no such algorithm exists, but you only need to prove it.
Proving that either P=NP or P!=NP is pretty much like prooving Fermat's Big Hunch - one of the Holly Grails of CS research. The problem is that we're not even close to such a result. It's interesting, though, that a lot of research is based on the assumption that P!=NP and not P=NP
... no one has found it (it's as ellusive as the concept of hyperspace)
Sure, finding a polynomial solution (ant not even O(n)!) for any of the NP-complete problems implies that all of them are solvable in polynomial time (they're polynomially reducible to each other), but
And, BTW, only cracking the key in RSA is NP-complete. One could crack the message without cracking the key first (theoretically speaking)
The Raven
The Raven
Of course, here he can post stuff for free, and have it seen by a wider audience.
autopr0n is like, down and stuff.
Whoever proved that an NP problem could be solved in some linear time would probably end up getting put in jail by Verisign or RSA as publishing a way to defeat their software. Then the FSF would have to step in, we would see a bunch of posts on /. about it, and then the Feds would finally get some brains and let that person go.
Doesn't this seem vaguely familiar? Are we in an environment today that really allows us to do what we want with computers or even our minds?
Just imagine a beowolf cluster of Turing machines...
wow.
...I'd break the news a lot like Linus did when he released 2.4.
"Oh, and by the way, here's the solution to some NP complete problem..."
Help us build a better map!
To answer the question about crypto then, will it break? Yes, definitely, crypto as we know it will break. Public Key Crypto is effective because the time to generate a private key from and unknown bit of salt and a private key is NP. That's why people don't brute force PGP... the naive brute solution is exponential in n, where n is the length of the key (2^n, where |n| is in bits).
But here's the rub: If you reduce such a problem to linearity (O(n)), then the only protection you have is increasing the length of n. But, to encrypt a message is still in O(n)*.
So, protect yourself with larger values of n all you like, but it takes exactly as long to crack a message as it does to encrypt one.
* the oddity is that it takes more time than O(n) to encrypt a message. But, it is in P. and if P=NP, the all polynomial time algorithms are O(n). Kinda sounds silly at the end of the day...
[b]A[/b]ffect, dipshit, [b]a[/b]ffect.
It would only mean that NP-complete problems would now have a polynomial solution. It would *not* contrain the exponent of the polynomial, so they could still (and likely would still) be very hard.
Most crypto algos are not NP complete. You can solve 'em it just takes a ton of time (but you can calculate how long it's going to take.) Doing NP complete problems in O(n) time won't help you break crypto at all.
autopr0n is like, down and stuff.
The very first consequence would be the discoverer being arrested for having violated the DMCA. And the second would be to threaten/arrest all algorithmic mathematicians working on the problem and likely to understand a word of the solution.
--Martin
The only thing that would suffer would be algorithms based on that class of problems. Unless someone found a way of solving the entire class of NP-Complete problems. By their nature, i seriously doubt if it is possible to solve beyond a single type of problem. It would require some sort of interrelationship between problem sets. If something on that magnitude were found, the benifits would greatly outweigh the drawbacks as we would have made a great leap forward in the understanding of mathematics.
"Trademarks are the heraldry of the new feudalism."
Make press releases. Submit papers to several different journals. Put it on different websites. Hand it out on flyers at the mall. Make sure that it becomes widely available before it can be caught and hidden by a small group. While there is some downside, it doesn't compare to having the solution be in the hands of a small group.
Why not read about Turing, especially from Andrew Hodges excellent biography. it provides wonderful insight to the entsheidungsproblem and other issues about computing. Basicly, it won't happen. It can't happen.
They would only arrive slightly faster. There are simulated annealing algorithms that solve the problem in O(n) with good (but suboptimal) solutions.
Toronto-area transit rider? Rate your ride.
assuming this made RSA encryption easy to crack by factoring primes (or whatever)
wouldn't regualar 128 bit encription be considered stronger?
They can crack RSA crypto in O(n^123,312,352) The world is doomed!!!!
'polynomial time' can still be a long-ass time.
autopr0n is like, down and stuff.
If you had such an algorithm in hand, what could you do with it? It would be interesting to see how many problems we could map into the NP Complete model.
Strictly speaking all problems where you can verify that a solution to the problem is correct (in polynomial time), could be solved by your algorithm. Or put another way: if you're able to formulate your problem in strict mathematical terms (using an IP, BIP or MIP) you should be able to solve it.
Perhaps the most obvious thing that would happen is that all theory about P, NP, NPC and complexity in general could be thrown away. No point in describing difficult problems with strict theory if they all can be reduced and solved as simpler ones.
http://www.mathsoft.com/asolve/plouffe/plouffe.htm l
"Sanity is not statistical", George Orwell, "1984"
although we cannot solve np solutions easily these days, there are many methods of approximation. some np complete problems, such as the travelling salesman problem, are easily modeled by things like the self organizing kohonen neural networks. although it does not technically find the optimal solution it is used quite widely in the real world to find a solution VERY quickly and as a VERY good approximation... i don't know much about too many other np complete problems, so i'm not sure if approximation would suffice. afaik, factoring large primes is np complete....but clearly approximation is NOT good enough.
QED
BSD is for people who love UNIX. Linux is for those who hate Microsoft.
I'm sure there must be a story about Linux possibly being defamed somewhere that could have been posted instead.
"The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers."
- Bill Gates, _The Road Ahead_
Sorry, that was a question?
If you could do that, publish it.
Stuff the collateral damage, that in itself would be a major achievement.
Sciene is not progressed by discovering things and keeping them to yourself...
Cheers,
Tim
It's official. Most of you are morons.
Firstly, an affirmative answer to the NP=P? conjecture only means that there is a solution to every NP-complete problem in P. That is, there exists a solution for every NP-complete problem that is O(n^d), where d is a constant integer. If d > 3, the solution would be practically infeasible anyway. Furthermore, even with an O(n) problem, this only means that the computational complexity approaches C*n in the limit of large n, where C is some constant. If C has to be arbitrarily large, or there exists a large constant additive factor in any potential solution, again the solution is infeasible.
Furthermore, the security of public key cryptography does not rely on NP!=P. It is not known whether the discrete-log and integer factoring problems are in NP (I think ... correct me if that's wrong). In fact, some CS researchers believe public key cryptography to be insecure, since some brilliant person could come up with a feasible factoring algorithm tomorrow, without requiring that NP=P.
Toronto-area transit rider? Rate your ride.
Not all encryption schemes are NP-Complete! Most are actually just NP-Hard because you can't tell whether or not you've found the correct decryption. So, decryption schemes will not be solved even if you can convert into NP complete problems into NP problems. It will be a lot easier though.
That polynomial can still be huge, say N^1000. Except for really large N, current exponential-time algorithms could be superior to polynomial-time ones.
This lacks some of the insight into NP and NPC problems. We only care about the large cases for the most part. On the small scale (small being relative to the problem), exponential solutions are always easy to solve.
There are some amazing implications of this anyway. For instance, we can solve chess (find the best possible game), and all other decidable search problems.
Keep in mind that our computer improvements allow us to make polynomial time reductions in the amount of time that the problem takes.
Mod me down and I will become more powerful than you can possibly imagine!
I wouldn't worry much about this. Almost all computer scientists believe that P != NP, and a lot of very smart people have put in a lot of time trying to show otherwise. Besides, even publishing a proof of P=NP does not mean that we can solve NP-Complete problems easily (could be huge exponents involved) and does not make encryption usless overnight.
Besides, cryptographers would very quickly start using much larger keys and eventually move into algorithms whose keys cannot be broken by solving NP-Complete problems.
Ben
and send it to some orbital gambling station where nobody would find it.
Sigmentation fault - core dumped
I presented this once before, but here it is again. I have a formula for finding the prime factors of a number, as long as the number only has two prime factors (this is usually the case for encryption). Here it is:
Let's say r = p * q
p and q are positive prime integers. If we are given r, we can deduce p and q with the following:
p = GCD(r, floor(sqrt(r))!)
q = r/p
GCD is the "greatest common divisor" function (quickly deducible with Euclidean math). This works because if a number only has two factors, one will be less than its square root, and the other will be larger (assuming p != q). In this case, the product of all the numbers less than the square root (the factorial) will have exactly one factor in common with r, and the GCD function will extract it. There's just one problem with this formula: for numbers as large as those used in encryption, the factorial will return a number too large to handle. But if we could find a good way to simplify the above equation without fully expanding the factorial, current encryption methods would crumble.
BTW, there are types of encryption that use chaos theory that would still stand strong.
For every post, there is an equal and opposite re-post.
The thing we would get if someone were to find a polynomial-time algorithm for any NP-complete problem is an immediate, poly-time algorithm for every NP-complete problem. This is because the definition of NP-complete is that there is a (known) poly-time algorithm to turn any one NP-complete algorithm into any other, so just by composing these two you get them all. (I'll attach a glossary at the bottom -- most people on this list probably aren't mathematicians :)
But OK, what does this mean realistically? The good news is that there are several very useful NP-complete problems; probably the best known (as someone has already mentioned) is the travelling salesman, and being able to do fast TS problems could mean incredible reductions in cost for shipping of goods and things like that. All sorts of problems in computer network architecture are also NP-complete; think about trying to design an internet which is both fault-tolerant and maximizing bandwidth.
The bad news: There are two things. First of all: This does not mean encryption of any sort is broken! The heart of public-key crypto is that factorization takes exponential time (or more specifically, the discrete logarithm, which is at the heart of fast factorization, takes exp time) and so if you could do poly-time factorization, you could break various algorithms like RSA. But factorization is only conjectured to be NP-complete; there is no proof, and in particular the explicit algorithm which would be needed to use a poly-time algorithm for some other NP-complete problem for factorization isn't known. This doesn't mean it can't be done; it just means that there's one other significant step between finding such an algorithm and breaking crypto.
The second problem is that even a poly-time algorithm isn't necessarily useful if the coefficients are large. What poly-time really means is that, in the limit of very large inputs, computation time doesn't go completely out of control; the fact that (to the best of current knowledge) factorization isn't poly is what makes adding one digit to key size enough to increase the difficulty of decryption by a factor of two. (i.e., the work increases as an exponential of the input) So this is important when you're trying to create "sufficiently large" inputs to jam up an algorithm. But for real-world problems that people are trying to solve apart from crypto, an O(N^1000) algorithm might technically be "better" than an O(e^N) algorithm but practically still be way out of reach.
In fact, most of the interesting NP-complete problems such as travelling salesman are routinely worked on by methods which give approximate answers in fairly short time; this turns out to be more than good enough for a remarkable range of uses, which means that the advance of getting poly time wouldn't be as earth-shaking for most real-world applications.
One thing to remember too, is that for many of these problems, e.g. the traveling salesman problem, approximate solutions can be computed quite quickly through various combinatorial optimization approaches. While having an exact, provable solution would be nice, if your willing to accept a "close enough" solution, having an algorithm that reduces it in polynomial time won't make much difference.
Even linear problems can take a long time to solve. Remember that algorithmic order represents asymptotic behavior -- how does the algorithm perform as the input size goes to infinity? A linear algorithm where each operation takes a trillion clock cycles will, in practice, be much slower than a quadratic algorithm where each operation takes only one hundred clock cycles; at least for "reasonable" input. In the real world, N does not go to infinity!
NP is funny. Like N pee.
Huh-huh!
Hmm, I think I have to clarify something here. As long as there's a key or 'shared secret' involved, decryption is an NP problem. Go check the definition: an NP problem is a yes/no question such as if the answer is 'yes', then it can be proven in polynomial time (O(n^t)). That's the case here: "Is there a key to decipher this?" can be rapidly given a positive answer once you actually do have the key. It's also most probably NP-complete, but the margin is too small for me to demonstrate it here. :) (You demonstrate that by proving a given problem is polynomially equivalent to a typical NP-complete problem such as SAT).
-- B.
This sig does in fact not have the property it claims not to have.
In real-world situations, you don't have accurate data for the cost of each link. Only approximations, built on probabilities of delays, estimates of how many packages will be ordered, etc.
The miniscule gain of selecting the best possible path rather than just a very good path would likely be reduced to an imperceptible gain when applied to rough real-world estimates.
There would be some extremely important consequences of P=NP, but direct application of a faster optimal solution of the Travelling Salesman problem to real-world travelling is not likely to be one of them.
It would mean a linear(O(n)) solution to all NP-Complete problems. Since it's proven that any NP-Complete problem can be translated into any other NP-Complete problem(that's how you prove NP-Complete by the way) a solution in linear time to one is a solution in linear time to ALL of them.
This would pretty much mean computers can do in linear time the most difficult problems we've found. These problems have enormous practical applications... The bin problem(filling an infinite series of 1.0 size bins with a infinite stream of fractional 0.13 0.35 0.80 pieces in an optimal fashion) can be used in an OS scheduler.. The traveling salesman problem in airline routes, etc.
It would also tend to imply that computers can do anything humans can.
The first thing that would happen after creating such a solution would be the FBI showing up at your door without a warrent and arresting you under the DMCA.
I'm pretty sure factoring is in NP. (The solution will be polynomial in the size of the input, and verifiable in polynomial time.) If someone were to prove P=NP, we'd have "fast" solutions to all of the problems in NP, not just the NP complete ones. (That's never gonna happen though..!)
in addition to optimizing the routes, the algorithm could be tweaked to make hijackings more difficult. Assign the flight numbers & routes at gate time, say. And you could even program the jets to fly straight up, sending terrorists into the lavatory. The best most ironic part is that John Ashcroft ends up funding open source!
Prove that it's impossible to solve NP-Complete problems in linear time, before someone figures out how to do it.
dinner: it's what's for beer
Oops, I didn't mean to say "NP Hard" in the subject line. It should say, "Factoring is in NP".
EVERY np complete problem can be mapped on any other (because it can be expressed in a simple logic language, and given one of the solutions you can generate any other by doing math with the solution you have). If you can calculate something that takes infinite processing power, you can calculate any other thing that requires that same amount.
... you can destroy public key encryption in a simpler way ...
...
... "Fundamenten van de informatica" by B.Demoen
The implications would be simple yet brutal, breaking a key of 128 bits would require 128 times the amount of time to break a 1 bit key.
There are still stronger mathematical formulae, but they must have continuous key spaces for encryption to work, if they want to defeat this, in other words, you will not only need an infinite amount of possible keys, but also an infinite amount of keys between any two given keys.
But that's not more than normal
The security of PKE is that you cannot easily determine the exponent of a given number. In other words given a and (a^n mod m), you cannot easily determine n. Right now there are algorithms that only work if n complies with a simple restriction. The alternative to that method is trying everything out. If some smart mind can generalise those algorithms we would have lost encryption as we know it
I only know a dutch text discussing this
"It would be interesting to see how many problems we could map into the NP Complete model."
The point is, everything that is not NP-complete, and still computable that has been found by man to date, is NP-complete (that is, exponential; O(a^n) for some a). The definition of NP-completeness is that it, using an algorithm of polynomial complexity (or O(n^a) for some a), can be mapped onto any other NP-complete problem, and thus solved using algorithms for it.
Thus, if an algorithm where found to solve one specific NP-complete problem in polynomial time, all of the NP-complete problems would be possible to compute in polynomial time (polynomial time to map it onto that particular problem for which we have the algorithm, plus polynomial time to solve it, and a polynom plus another is still a polynom).
Trivia: The "standard" NP-complete problem is SAT, which is the problem of finding out if there exists assignements of truth-values (TRUE and FALSE) for the variables of a logic formula, that makes the value of the formula TRUE.
--The knowledge that you are an idiot, is what distinguishes you from one.
If this is a troll, it's a great one. Otherwise, you are an idiot.
the Charles Stross short story "Antibodies" deals with exactly this question. It can be found in this "the years best science fiction" anthology - very good story
Some of the implications of P=NP were explored by the UK author Charles Stross in "Antibodies". You can read it in "Year's Best S.F.:18" ed. by Gardner Dozois.
i thought the point was another goatse link
since both the beatles and stern are total shite, the hendrix comparison seemed out of place
there's more than one way to do me.
This lacks some of the insight into NP and NPC problems. We only care about the large cases for the most part.
How large is large? 2^128 (for brute forcing common encryption) is pretty much impossibly large, but is 128^1000 (to use the original poster's example) really an improvement?
Actually, there has been an NP complete problem solved in P time. Peter Shor in 1994 published an algorithm for factoring large numbers in P time using a QUANTUM algorithm, not a classical one. AFAIK, scientists have Los Alamos have also built one of these to factor the number 15 (woohoo).
Does this mean that RSA is going to die anytime soon? Unlikely unless a breakthrough in quantum computing occurs in the short future (look at how long it took for transistors to get up to super speeds).
Using quantum properties, there will probably be more NP complete algorithms that are found to have polynomial solutions, but it is a realitively new area, so we'll see what happens. And remember, if it's not quantum, it's crap!
What if I had an algo (or heuristic) that would produce, not necessarily the best answer, but one always within 1% of optimal, all in O(n)? Would that have the same practical effect as a true solution in O(n)?
.micah
--- Learn XForms today: http://xformsinstitute.com
Just one point: Whether or not Factorization is NP-Complete, a poly time solution to an NP-complete problem would imply a poly time solution to Factorization. This is because an poly time algorithm for an NP-complete problem implies poly time solutions for all NP problems: that's the definition of NP-complete and what makes that class interesting.
NP (non-deterministic polynomial) problems are precisely those class of problems for which a non-deterministic turing machine can guess a solution and verify it in polynomial time. Thus, for question X, if an answer can be proven correct or incorrect in polynomial time, then X is in NP. Factorization is in NP since, given the correct factors of a large number, those factors can be multiplied quickly to prove they are the real factors.
> Similarly, we know there are an infinite number of primes, just that nobody has been able to prove it.
/ in finite/
Actually there are loads of proofs of this:
http://www.utm.edu/research/primes/notes/proofs
Otherwise I agree with your sentiment...
Somebody help me, but there's even a paperback book available on the story.
So, this question came up in an algorithms class at Princeton. To the best of my memory, the slide answering it said:
"What if P = NP?"
"BAD:
- Many computer scientists out of work
GOOD:
- Perfect societal bliss"
The point is essentially this: verifying the value of an answer to an optimization problem (of any kind) is usually easy. But finding a better solution is usually hard (exponential). So, saying "P=NP" is equivalent to saying "Finding an optimal answer is not really harder than verifying if an answer IS optimal." So, finding the optimal design for an aircraft, the optimal routing for a network packet, the optimal anything, is not really that tough. And that wouldn't be such a bad thing for our society (though "perfect bliss" was probably an exaggeration).
and let the chips fall where they may.
Information wants to be free.
It wouldn't be the first time whole industries got brushed aside by advancing technology, either.
You should have heard the way the buggy-whip consortium bitched when those damn horseless carriages came out. Man, there was gnashing of teeth.
And the telegraph industry is now a mere shell of the monolith that it constituted before AGBell came around with his damn telephones.
Look at the passenger train industry, if you can find it. Those Wright brothers and their damn airplanes stuck a stake into its heart.
Do you expect me to mourn the passage of RSA when something better blows them away?
And what about the Borg? Proprietary OS software doesn't have a prayer against Open Source Development, yet the Monopolist refuses to give up.
I guess all these guys are to be admired for their tenacity, but you have to understand that it's their livliehood that's at stake. Of course they aren't going to give up without a fight!
Exceeding the recommended torque is not recommended.
Finding prime numbers (the basement of the encryptions algorithms) is a NP problem. But it is too in the Co-NP class. This is very important, because all of the problems that were in both classes in the past are really P problem ! So... the only one problem that is at the present in both NP and Co-NP classes is the primality problem !!! Brrrr..... :)
Large in this case usually means infinite:) It's all about how the function t(n) behaves where t is the time necessary to compute the value of a certain function f(n) relative to n; it's not about comparing 2^128 to 128^1000 but about comparing 2x to x^2 and 2^x to log(x). Read Herbert S. Wilf's Algorithms and Complexity if you want to know more about it. It's the book we use in school (and it's downloadable for free).
0x or or snor perron?!
someone mod up the parent saying why factoring IS in NP.
The post above that says finding a solution to an NP complete problem does not affect factoring, but it does. It is a known fact that factoring is in NP. It is not known if it is NP complete.
In other words, if you figure out how to factor fast, you can't do anything else fast necessarily. But if you figure out how to solve travelling salesman, you can solve factoring.
A boon to traveling salesmen everywhere!
:-)~
Could you be more racist?
Open up your eyes and get a life.
We can make polynomial improvements by getting better hardware for most problems. What we can't do is make exponential improvements. This is why it is trivial to solve most kinds of polynomial problems.
All NP-complete problems can be considered search problems. All search problems can be parallelized.
Mod me down and I will become more powerful than you can possibly imagine!
I'm not sure it's obvious what the answer would be. For example - would we be able to cure cancer? You might just say "simulate the whole human body and simulate throwing a googleplex different drugs at it". But in order to do that you need to have an accurate physical model - accurate down to every molecule in a person. That's still hard.
So imagine an 'oracle' like this suddenly appeared somewhere. What impact would it have on society for the next few centuries?
(There's also the issue of what kind of interface this device would have. Lets say it has some kind of serial port that appears to be able to respond to signals sent into it no matter how fast they are).
-- SIGFPE
Other posters have pointed out that this was proved clasically (and by classically I don't mean last century, I mean like 500BC or whenever Euclid was around), but not only is this a classically known fact, I will reproduce the simplest proof I know here:
We will prove this by contradiction. We will assume that there are a finite number of primes, i.e. that there is a largest prime. Let's number them p_1,...,p_n.
To show N is prime, it suffices to show that it cannot be divided by any smaller number (except for 1). Even better, it suffices to show that N cannot be divided by any smaller prime (since if a smaller number divided N, so would its prime factors). Consider the number
N = p_1p_2...p_n + 1
by which I mean that I multiply all of the primes together, and then add one. If I can show that this is not divisible by any of the primes, I am done. But consider what happens if I divide N by any p_k. Looking at the formula, p_k certainly divides the product evenly, so therefore if I divide N by p_k, I always get a remainder of 1.
Thus N is not divisible by any p_k. But thus it is not divisible by any smaller number, and therefore is prime. But since N > p_n, our "largest" prime, this is obviously a contradiction. Therefore there can be no largest prime, and thus there are infinitely many.
As I said, this proof is due to Euclid. There are many sources for this proof, and there are many other elegant proofs. There is a realtively advanced book called Proofs from the Book which gives elegant proofs to some well-known (and perhaps not so well-known) results. This is a nice little book, and, anyway, there are no fewer than six proofs that there are infinitely many primes. Not being a number theorist, I don't get all stiff about primes personally, but it's good stuff.
Come on, give it up, that's
First of all, solutions for most NP-complete problems can be solved in much better time than exhaustive search. However, the solution of one problem does not imply the solution to any other NP problem. This is one of the important defining characteristics of NP problems: they are not related in any way to any thing, structure, or each other at all. That is why generally the only way to solve certain special NP complete problems is through a brute force search of the entire solution space which may be so large that it is impractical for such a search. An algorithmic solution that produces a solution faster than brute force search implies a structure to the problem that by definition, NP problems do not have.
It is generally believed that all NP complete problems are also extremely difficult. In fact, you only hear about the really hard NP problems that make the entire class of problems famous. There are techniques for example that very effectively "prune" large search trees. Yes the search space can be huge and yes there is no algorithmic way to locate the exact solution, but huge portions of the search space can be disqualified from the search making finding a solution very efficient in most cases. The N-queens problem is a good exmple of this principle. On an NxN chess board, find all configurations of N queens such that no queen is in a position to take another queen in one move. For a board with even N = 15, the search space is absolutely massive. A simple minded program could take several years to solve it. There is no algorithmic solution to this problem. It is NP complete. However, much of the search space can be eliminated by simple prunings such as: any solutio n with 2 queens adjacent to one another need not be searched, etc. A well written program that takes advantage of huristics like these can solve N-queens in nearly linear time. Most NP-complete problems fall into this class.
Apparently, there is a ratio for NP problems that can be expressed as a set of binary equations between the number of variables and the number of clauses where NP problems are truelly difficult and no known technique can reduce the search space significantly. I think it is something like 2.1:1
I know that last part sounds assinine and I don't really understand why, but I swear I've seen run times for hundreds of variables and clauses range from a few seconds at ANY other ratio to taking hours to longer than I cared to wait for sets of equations at that ratio.
(I took a very cool AI class last winter.)
If such a discovery were ever to be made, the only responsible course for the discoverer would be to keep the discovery a secret, and to form, as discretely as possible, a society of Custodians of the knowledge, whose task it would be to keep the O(n) solution safe. By applying their knowledge in secret beneficial ways, they could subtly steer the course of Mankind's history towards a future time when they would be sufficiently prepared to deal with the consequences of the O(n) solution.
The organization would, of course, have to be composed of all the top computer scientists in the world, and would have to continually recruit all of those intelligent enough and close enough to coming upon the discovery on their own. On the other hand, in the classrooms, the old dogma would have to perpetuated to keep society safe from the disastrous effects of a premature disclosure.
If--and I say IF--one of us slashdotters should stumble upon such a discovery, I should hope he would realize the Promethean significance of it, and refrain from submitting it to Taco or whomever. I have been studying and thinking about the science of Psychohistory for a long time, and have meditated profoundly over the works of Harri Sheldon. I would be glad to provide my aid in constituting the Society. And please respond via private e-mail.
Somebody want to explain to a non-mathematician (only in 1st year university, gentlemen) what P and NP are?
I'll give you a cookie if you do, and undoubtably you'll get a +5 Informative.
If NP complete problems were reduced to O(n), then that would be *FANTASTIC* -- amazing beyond belief I tell you! Because the current conjecture that NP > P >= O(n), would also mean that all *POLYNOMIAL* problems were reduced to O(n)! I.e., bubble sort could be made just as fast as quicksort!
Guys, consult a mathematician before you blather on matters mathematical. The interesting case is if NP = P (which is not the same as O(n)). This would mean that there was some maximal polynomial at which all NP problems could be bound; which would be interesting -- the real implication being that Moore's law would eventually be able to out run a large class of interesting math problems.
I'm not 100% sure, but I think it may mean that we can go track down Ramsey numbers using brute force as just a matter of time and compute power. And yes, cryptography in its current form would fall.
false.
Definitions:
P is a class of problems that can be decided by a deterministic turing machine in polynomial time.
NP s a class of problems that can be decided by a non-deterministic turing machine in polynomial time. It means (literally) non-deterministic polynomial.
A problem is NP-Complete if:
1. It is in NP.
2. Any other problem in NP can be reduced (read: "converted") to it in polynomial time.
So, if a polynomial-time solution to an NP-complete problem is ever found, any other problem in NP will automatically have a polynomial-time solution. That includes most of the known algorighms.
Oh, and just to preempt stupid replies saying "it depends on which NP-complete problem is solved" or "perhaps the problem is misclassified": read the definition again. Any problem in NP can be reduced to an NP-complete problem in polynomial time; including another NP-complete problem.
Finally, a description of what P ?= NP question is:
P is a subset of NP (obviously). The question is whether it is a proper subset (i.e. P is strictly smaller than NP) or P and NP are actually coincident (i.e. P = NP). The answer so far is "probably not". There is a large number of NP-complete problems and so far no one has been able to come up with an efficient (i.e. poly-time) algorithm to solve any of them. However, P = NP implies that such algorithm exists (and vice versa).
(Stupid slashdot filter deletes less then signs)
___
If you think big enough, you'll never have to do it.
It doesn't surprise me any more when Slashdot displays large amounts of ignorance about non-computer topics, but I expected better for something like this. I've been skimming through the +2 and higher comments, and not a single poster has defined NP-complete correctly (this may have changed by the time you read this, but it was true when there were >50 comments at 2 or above).
Here's the correct definition of NP-complete:
To be in NP-complete, a problem must be in NP--that is, it must be a concrete decision problem, and have a polynomial-time verification algorithm (i.e., if somebody hands you a solution to the problem, you can verify that it's correct in polynomial time). Furthermore, there must be a polynomial-time mapping from every problem in NP (not just NP-complete) to your problem.
My source for this is Introduction to Algorithms, by Cormen, Leiserson, and Rivest (yes, that's THE Rivest of cryptography fame), which is part of the MIT Electrical Engineering and Computer Science Series.
Now, some people have been getting confused and saying that being in NP-complete only requires there to be a polynomial-time mapping from every problem in NP. This is an understandable mistake, since the way one usually proves a problem is in NP-complete is by finding a polynomial-time mapping from one NP-complete problem to the problem of interest (which must already have been shown to be in NP). However, since you already know that there are polynomial-time mappings from every problem in NP to the NP-complete problem, there is thus also a polynomial-time mapping from every problem in NP to your problem. The difference here is that efficiently solving an NP-complete problem means you can efficiently solve all NP problems, not just the other NP-complete ones.
The second big error--the one that boggles my mind--is that the poster seems to have confused O(n), which is linear time, with polynomial time. True, O(n) implies polynomial running time, but polynomial-time does not necessarily imply O(n)--you could have O(n^2), O(n^3)...
The third mistake is the implications of any polynomial-time solution to an NP-complete problem--even if it is O(n^1000). A few people here are claiming a polynomial-time solution would be irrelevant if the order of the polynomial was large (giving O(n^1000) as an example of large). For moderately large inputs (and we're really not talking that large), O(n^1000) is better than O(e^n). Taking the example of O(n^1000), n only has to be greater than 10,000 for O(n^1000) to beat O(e^n). Exponentials grow fast, people.
Finally, getting to implications, any polynomial-time solution to any NP-complete problem would instantly destroy public-key cryptography. Even if everybody immediately switched cryptosystems, the implications would be staggering, because someone could have archived all sorts of encrypted transactions, the contents of which are still sensitive. My understanding is that prime factorization is in NP, but not in NP-complete (not that this matters too much, as I explained earlier). Not sure about the math other forms of PK crypto are based on, but I suspect it's also NP.
On the plus side, protein folding simulation is suspected to be in NP (this may have been proven--not sure). If you could do protein folding simulations efficiently, it would make finding a cure to most diseases a hell of a lot easier (and we'd finally be able to figure out what the hell the human genome means).
Pardon me, the fourth paragraph should read:
Now, some people have been getting confused and saying that being in NP-complete only requires there to be a polynomial-time mapping from every problem in NP-complete, and that it does not imply a mapping from NP in general....
The question, "Is there a program of length n that passes this test suite in polynomial time?" is NP-complete. Algorithm: guess the program, then run it through the test suite. I believe an O(n) algorithm for that would make mighty big changes to computer science.
Can you rephrase this? It sounds like you are saying that we can/could determine the best moves in chess.
"The only rights you have are the rights you are willing to fight for."
Large in this case usually means infinite:)
Yes, I'm sure the previous poster knew that.
The asymptotic performance of an algorithm is not everything; if you actually want to use it, constants matter too. (ask your algorithms teacher why everyone isn't using the linear-time mediant algorithm for their quicksorts, for instance)
The point the previous poster was making (which I will remain agnostic on) is that if someone manages (heh) to prove that P=NP, solving a given NP-complete problem might have such a large constant or (worse) exponent that for PRACTICAL PURPOSES it doesn't allow us to do anything new.
Daniel
Hurry up and jump on the individualist bandwagon!
E = MC2
The simplest problem to understand in NP space is optimization. EVERY optimization problem is NP-complete. If you want to find the shortest route to visit every city in the US, this is an optimization problem.
What a problem being in NP-complete space means is that if you can solve one problem in the space, you can solve all problems in that space (by transforming the other problems to look like the solved problem and then solving that).
So if you prove P=NP, then you can solve optimization problems in polynomial time O(n^t). Pick a problem where you could say "I wonder what the fastest/shortest/lightest way of doing this is?" and you could solve it in O(n^t).
4 caveats/common misconceptions:
O(n^t) could be very VERY large. n^237203 still takes a very long time.
As far as I know, encryption algorithms are NOT KNOWN to be NP-complete. So it's UNKNOWN what proving P=NP means to the encryption world.
People who say P=NP is not provable aren't conveying the situation. The situation is that it is UNKNOWN if P=NP or not. They don't know the answer.
There are problems that do not fall into NP-complete class. There are NP problems that are not complete. There are (provably) problems that cannot be solved. So P=NP doesn't really act as a cycle multiplier (you don't just get more pure computation), it just gives you another trick in your bag.
So my answer for what happens if P=NP is proven: Everything in the world gets cheaper.
passetspike!
Pure Gold!
It's interesting how most of the answers here fail to look at the actual question. The question wasn't so much, "what will break;" the question was, "what should one do."
Although it's interesting and even essential to review what parts of computer science or our economy would be toppled by such a discovery, doing so doesn't answer the question.
Let me rephrase the question for any who missed it: "Suppose you discover that P=NP. What is the right thing to do?" Do I cover it up, or do I release? What if I proved that P=NP, but I don't know of an algorithm to actually convert any known problem? Or, what if I did know the algorithm and the proof, and I believed that the algorithm couldn't be reconstructed from the proof -- should I release the proof?
This is a powerful question!
My feeling is that the truth should be known, but experience shows that information without knowledge, and knowledge without understanding, can be deadly. (I'm afraid you can't affect whether people will get understanding without wisdom, so we'll stop the natural progression before we reach that point.) A little survey of the literature (please see the other posts here; they've got GREAT info) shows that the practical benefits of this discovery would be IMMENSE. The drawbacks seem huge, too; but if a particular algorithm has become easier to destroy, so also do new algorithms open up. Look around -- identify as many existing things which are harmed by your discovery, and try to provide a discussion of how to recover from the harm.
Even if you're not altruistic you want to do this; the person who is most essential in the new world isn't the person who discovered the info, since once the secret's out it's not under his control; it's the person on whom people are depending. Be that person -- but don't be selfish about it. Too selfish ruins the game too; there's always someone with enough power to take your position away from you.
So that's my knee-jerk answer, with a bit of reasoning: research the discovery, find who it hurts, and prepare to help them. Then make it public.
There's another question which is implied by the first one: to whom do I release info about my discovery? I can't answer that. Does anyone have an answer? I can say that you'll HAVE to release some information before you're ready to release it all; for example, you might want to found a corporation, and you'll almost certainly need library assistance. What can I say about that? Pick people you can trust, and don't trust them with too much.
-Billy
Just because something is not known by everyone else, does not mean that someone one(or government) hasn't already figured it out and keeping it all to themselves.
...that the original classification as NP-complete was wrong. "We thought we had a hard problem, but we were wrong." This would typically mean that the original paper had a bad proof -- not an unknown event. Another possibility is that a hard general case has a much easier special case, and the special case maps usefully to real-world problem sets. Again, not an unknown event (perhaps a good description of fluid dynamics -- impossible theory but useful praxis).
So while you're absolutely right at the mathematical end (and there were too many pseudo-conclusions posted here, no surprise), from a practical standpoint the question is valid: what if it turns out that there is an easy solution to a hard problem, a problem whose hardness we had viewed as a practical limit? (And this isn't a mathematical or CS problem, but a political issue.) I suppose this interesting question was just phrased in "look how smart I am" terms.
-- We all have enough strength to endure the misfortunes of other people. La Rochefoucauld
P=NP if P = 0 or N = 1, right? Maybe I'm missing something?
Given advances in alternate methods of computing, such as quantum computing, NMR computing (ensamble quantum computing), and DNA computing, to name a few, there is good reason to consider such a question.
It is also ironic that the examples of unsolved problems given may certaintly at one time have been considered intractable, but several have now been decided. Similarly, although it is not obvious now how to do it, it does not seem too incredible that it could be solved in the not-too-distant future.
"You call it a new way of thinking; I call it regression to ignorance!" -- Operation Ivy
NP problems are, loosely, problems for which you can check that the solution you have is correct in a time that is a polynomial function of the size of the problem. NP-Complete problems are problems that can be converted, in polynomial time, to the boolean satisfiability problem, and the answer to the resulting problem can be converted back in polynomial time.
:-)
Given a plaintext/ciphertext pair most block ciphers can be written as boolean equations that are satified by the correct key (you may need more than one pair to be sure that there is only one answer). Thus, if NPC=P then most block ciphers can be broken in a time that is polynomial in the key length.
Of course the order of the polynoial may be so high that you don't care that much, and indeed is the order is greater than the key length then it's no better than exponential time
If intelligent life is too complex to evolve on its own, who designed God?
Interestingly this was the premise of a story published in Analog Science Fiction earlier this year. The end result in the story was a not so nice form of AI made possible by the use of more efficient algorithms. Parts of the story also referred to some of the poster's concepts of failed cryptography, etc.
I wonder if the poster was 'inspired' by this story?
Actually, a theoretical computer scientist (Russell Impagliazzo) has already sort of answered the "What if..." question in this paper. It's an interesting paper and the "what if" portions shouldn't be too hard to read, even for those without complexity theory backgrounds.
NP hard problems will not be affected. The TSP and all the optimization problems are NP hard. NP complete means the solution can be checked in polynomial time, which is not true for optimization problems. Also factroring primes is not NP complete as there is no polynomial time algorithm yet to check if a number is prime.
Two women at the same time.
I was at an interesting seminar today where one of my professors was talking about how P=NP seems to pop up in a lot of areas. The most intersting thing is that we can solve many NP problems in almost guarenteed polynomial time by using random techniques. As pseudorandom generators evolve we are able to generate numbers almost totaly random to the computation at hand.
The question may not be does P=NP, but are problems solvable in polynomal time in the same class as problems that can be solved using random methods, a class called BPP(Bounded-error Probabilistic Polynomial).
bash-2.04$
bash-2.04$yes "Don't you hate dialup connections?"| write USERNAME
Is a NP complete solution sometihg I can do on my linus beowulf cluster? If so I can stop runnnig my favorite game of Doom, and devote some of my cluster boxes to this problem instead.
A few theory things to clear up:
1) Completeness. A polynomial solution to any NP-Complete problem would mean that there would then be a polynomial solution to *all* problems in NP, i.e. that P=NP. This does in fact mean that the usual problems we assume to be superpolynomial for encryption purposes (i.e. factoring, discrete log) would have polynomial solutions, since they are in NP, though not believed to be NP-complete.
To check whether a decision problem is in NP, simply find a polynomial-length "hint" with which you can solve the problem in polynomial time if the answer is yes. For instance, satisfiability is in NP because a satisfying truth assignment allows you to check quite quickly that a formula is satisfiable. Discrete log is also easily seen to have such a hint (i.e. if you're told the discrete log, you can check quite easily that it actually is by exponentiating). Factoring is harder to show in NP, but possible.
2) Complexity measures for numbers. While we usually think of numbers having their own sizes (2 is bigger than 3, etc), when we talk about the inputs to algorithms being numbers, for compleixty purposes, we usually want to think of their size as being their length in binary digits rather than their size, since numbers get harder to deal with for addition, multiplication, etc. as their length increases (adding any two digit numbers is pretty much the same difficulty compared to adding three digit ones). So while we can factor n in time o(\sqrt n) by brute force, we really want to do it in time O((log n)^t) for some constant t. This is what would constitute a polynomial time solution here.
3) Large exponents. It is absolutely true that P=NP would only mean that there was a polynomial solution to factoring; this could still have a huge exponent and still be really slow. But I assume that the original poster was interested in the potential for a fast solution.
Assuming a fast solution to an NP-complete problem, yes, lots of public-key cryptography would break badly (much symmetric key would still be as safe as ever). The responsible thing to do would probably be to announce the solution with some lead time, after making arrangements for your own safety until the solution could be published widely. Though if it were actually satisfiability that we could do quickly, rather than just factoring, there would be lots of other interesting things you could do (solve many engineering optimization problems quickly, for instance, and use computers to prove most mathematical theorems fast...)
If in Atlanta during rush hour on a bad traffic day.....
The Answer is to get out of the car and start walking, unless you are lucky enough to have one of them Segways. Then you can fall you way there, and there and there.
That compaired to having stayed in your car.... You did better then NP complete.
Large in this case usually means infinite
It's always easy to tell who's getting their CS degree and heading off to the workforce... and who's headed off to never-never land for their Ph.D. Large in this case usually means 128 bits. Really. I know about asymptotic analysis; I'm talking about actual programs.
Don't take that personally, BTW... I'm currently in CAM never-never land, and I'm just pissy that the spiffy O(n lg n) Delaunay triangulation algorithm I invented this semester doesn't seem to beat the standard O(n^(5/4)) algorithm for any problem size small enough to test on the 256MB RAM in my PC.
I think I have this P=NP problem worked out. All you have to do is divide everything through by P. That way N = 1. Now where is my prize?
"I have a porkchop, you have a porkchop. I have a veal, you have a veal".
I have to say its wonderful to see TCS making an appearance on the front page of /. ... warms my heart.
Anyway, after perusing the comments (most of them quite good), I thought I'd point out a couple of common misconceptions in previous posts:
NP != EXP. Yes, for problems in NP the best *known* algorithms require exponential time, but no one has proven this to always be the case. Maybe we're just bad at finding algorithms (not likely though). All we can say for sure is that problems in NP require polynomial time on a non-deterministic machine. Non-determinism being the key problem here (and what forces these algorithms into exponential time when you run them on deterministic machines).
NP != BQP. E.g. you can't solve NP-complete problems in polynomial time on a quantum computer. There are two types of quantum algorithms out there at the moment, Shor-flavour and Grover-flavour. Shor-flavour algorithms can solve some specific problems (notably factoring and discrete log) that are in the intersection of NP and co-NP but are *not* NP-complete. Grover-flavour algorithms can solve database searching problems in O(sqrt(n)) time, despite the classical firm lower bound being O(n).
Its most likely that BQP and NP are disjoint so attempting to compare them may be a rather fruitless effort.
If the hardness of NP-complete problems really causes you to lose sleep, look into the field of approximation algorithms. In many cases we can get a very good solution, just not the optimal one. We can even given an upper-bound on exactly how 'bad' the solution we find is compared to the optimal one.
Just my two cents worth.
L.
This is BY FAR the nerdiest article I've ever seen on slashdot...
"You are not a beautiful and unique snowflake."...Tyler Durden
Aggghhh. I thought that I'd escaped from talk of NP-Complete problems after my "machines and algorithms" final on tuesday. Is there nowhere I can hide?
Well, everybody seems to have their own ideas about what the various classes mean. Your post contradicts what I thought, so I looked it up:
l
NP-Hard: From a solution to an NP-hard problem, we can solve any problem in NP.
NP: Can check a polynomial-size solution in polynomial time.
NP-Complete: Intersection of NP and NP-Hard.
Thus, NP-hard problems are "harder" than NP-complete in the sense that a solution to an NP-hard problem gives you a solution to any problem in NP-complete.
I am almost positive that factoring is in NP, since it should be straightforward to check a solution in polynomial time.
http://www.cs.unb.ca/~alopez-o/comp-faq/faq.htm
2x3x5x7x11 + 1 = 2311 is prime
but
2x3x5x7x11x13 + 1 = 30031 = 59x509
in not prime.
The important steps in the proof is supposing that {1,
See http://www.newphys.se/elektromagnum/physics/Ludwi
Check out what Google has...an excerpt
The field is motivated by the many concrete problems that are NP-complete or worse, yet can be solved in polynomial time with only an additive exponential contribution from some limited distributional aspect(s) of the problem (the parameter). The theory is built around this sharper analysis of feasibility extending polynomial time and includes distinctive and powerful algorithmic techniques to exploit parameterization. It is widely embodied in practical exponential heuristics, and involves a rich and concretely applicable structure theory based on miniaturizations of Cook's and other theorems.
A speech...
"For instance, we can solve chess (find the best possible game), and all other decidable search problems."
Can you rephrase this? It sounds like you are saying that we can/could determine the best moves in chess.
There are about 10^120 positions in chess, if I remember correctly. Even if you could solve it, there'd be no possible way to store the answer, as this is much larger than the number of atoms in the universe (around 10^80). As Dirk Gently might say, "If you can't possibly store it, then it must be stored impossibly!"
They who would give up an essential liberty for temporary security, deserve neither liberty or security
Can anyone suggest a solution to this:
:) Which means I need to find a way to burn X bytes of warez onto N cds. where (N-1)*650MB = X = N*650MB, N a integer, and X is closer to N*650MB than (N-1)*650MB. Would this turn into an NP complete problem?
I have a lot of warez on my computer and running out of disk space. I need to burn those warez to 650mb CDs. But I want to use the space on those CDs efficiently, since I am too cheap to waste space like that
Wroot
Additionally, if time was not an issue, you could solve this problem with very little memory using a simple depth-first-search approach. The amount of additional space you would need would simply be the depth of the stack. The depth of the stack is equivalent to the number of moves. The number of moves in a typical game of chess is less than 50, but what's important is that you can bound the number of moves by some constant.
"The only rights you have are the rights you are willing to fight for."
Not quite true; it is likely that the solution could be expressed as an algorithm that would take up much less space than an exhaustive list of state transitions.
For example, if you had a game where the goal was to take turns naming positive integers until someone was forced to name an integer larger than the one their opponent just named (and thus lost), there are an infinite number of states, but the "solution" can be expressed quite simply:
Say "one."
So, at least in this case, the solution is much smaller than the list of all posible cases. I suspect the solution to chess, while much larger than this, is still smaller that you propose.
-- MarkusQ
Most people have incorrect misconceptions about NP/NP-completeness since this often isn't covered in many CS degree programs. Let me clear up a few things people seem to consistently post incorrectly about.
First of all, what is meant (most likely) is that some NP-complete language can be recognized in polynomial time. The complete in NP-complete means that EVERY language in NP can be reduced (in polynomial time) to this particular NP-complete language. So P=NP.
NP is the class of guess and check languages. For example, we can see that determining if a number is composite is 'in NP' by guessing a factor. We can check by seeing if our guess divides the original number. If the total time for the guessing and doing the check is polynomial in the input length, then the language is NP.
P is a subset of NP. So when you say a particular problem is 'in NP,' this doesn't necessarily equate with an (even potentially) intractable solution.
There are only a few problems which are in NP that are not either known to be NP-complete or known to be in P. One of these is factoring of integers and forms the basis for RSA. Another is the Discrete Log which forms the basis for Elliptic Curve cryptosystems. Both would be essentially broken if P=NP, but so would most other things.
One of the biggest consequences of P=NP is that P=PSPACE. This means that many problems thought 'harder' than NP are also solvable in polynomial time. For example, the level of 'GO'-playing computers would increase. Just about every computational problem imaginable is within PSPACE, so if you are wondering would 'xxx' be affected, the answer is probably yes.
It is believed that recognizing whether a number is prime or composite is already solvable in polynomial time (in the input length) (ERH). However it isn't certain if ERH is true, so recognizing if a number is prime is technically NOT (necessarily) in P.
In practice, it is possible to make the decision with arbitrarily high probability. The fact that it is still sometimes difficult to factor is what makes the problem useful for cryptography.
I hope this clears things up some. Maybe people will stop wishing for O(n) solutions for NP-complete problems...
Why should that be a problem? If it really were the answer to so many real world problems then just use your new found solution to figure out whether to make it public (and how) ;).
If it doesn't work that way, then why worry: just publish it I'd say. Get your Nobel Prize, have fun, be good.
Finding answers to questions is easy compared to finding the right question in the first place.
Also with humans sometimes just talking is good enough.
"What's the problem?"
"Dunno, nothing"
blahblahblahblah about nothing much in particular, esp things both already know about, for 20 minutes.
"Hey thanks!"
Funny eh?
Cheerio,
Link.
The difference between theory and real life is in theory there's no difference.
packets visiting every other point on the internet
That would be infinite improbability powered internet.
Mmmmmmm
Because if you did, they should've known that prime factorization is not considered an NP-hard problem, but is more likely in neither P nor the hard subset of NP.
(Incidentally, it has been proved that either P=NP, or there exist problems that are neither in P nor NP-hard, of which prime-fac is believed to be one.)
That's exactly what I'm saying - we could find the absolute best.
By "solve" I meant, given that two computerized players both played a perfect game, who would win, the first player, the second player, or would it be a draw? This is the kind of question we could answer.
It seems impossible, but if you study AI a bit, you'll see that this is what NP=P implies, despite the seemingly enormous search space required by BFS, since chess is NPC. Obviously the solution wouldn't be using the BFS.
Mod me down and I will become more powerful than you can possibly imagine!
However, giving a near-optimal, approximative, shortest path is *not* NP Complete.
So if the providers have a lot to gain from not using an NPC problem and don't mind slightly less optimal paths, they'd go for that.
Beware: In C++, your friends can see your privates!
And exactly what pizza chains are doing this?
Dominoes was the only one that really ever offered it free if not delivered in 30 minutes and it's been what... a decade since they stopped doing it because of legal concerns with bad driving as a result of meeting the 30 minute mark?
First I assume you mean O(n^p), not simply linear.
Even if NP can be reduced to P, the transducer could very well be 10^100*x^(10^100). In fact it would be much more likely that the transducer would be some unwieldy polynomial. And as is often the case, the first one found would be very rough and would lead the way towards more streamlined functions.
The point being, while it would have very major theoretical implication immediatley, it may not have ANY practical implications
Come up with a proof and tell people about it. Even if it only helps optimize the factoring of large numbers by 10%, no one will understand that it doesn't change the security of encryption much and Mossad, Saddam, the CIA, and the NSA will be after you. And you'll be dead just like the nice mathematician was in the movie Sneakers.
</conspiracy theory>
--jeff (off to watch more movies)
ipv6 is my vpn
You are right; I meant P=PH, not P=PSPACE.
come on here people .... this is SO OBVIOUSLY a joke, you just have to laugh at him, and thank him for brightening my dull day ...
Well, I finished my theory final the other day, and unless someone tries to sell me a solver for an NP complete problem, I really do not give a horses ass about them... of course this could just be because I am burnt out from studying a semsters worth of theory, alrogrithms, and turning machines...
Wow, this is such great timing. I've been studying for my computability final for next tuesday and this was the topic that I didn't really get...
Anyways..just as a note, NP doesn't not mean O(NP) as many of you are talking about. O(n) is a term for speed of an algorithm. P vs NP problems deal with whether something is calculatable
If anyone has some free time and wants to win a million dollars read this: The P versus NP Problem (oh..did I forget to mention that you must be a genius in computablity) Here is the press release about the $1 million prize money.
_______________________________
"I'm not Conceited...I'm just a realist..."
I totally agree. And I would like to add that when a particular polynomynal time solution is found for a problem thought to be non-deterministically, this does not mean all NP problems are in P.
For example, the problem of parsing context free grammars (or mildly context sensitive languages) in the most general form was long thought to be non deterministic. Nowadays we have context-free parsers that operate within O(n^2), while there are particular problems, like the LALR(1) grammars applicalble to most programming languages, that operate within linear time. Still, many NP problems remain.
The misconception here is that non-determinism is usually incorporated into an algorithm in terms of some "enigma" which *somehow* makes the non-deterministic choice the right way. Then, the non-determinism is completely localized within this black box. Next, this line of thinking assumes that when a (some) problem that is formulated in terms of this enigma turns out to be formulatable in P as well, that in this case we have implemented the enigma itself in P. Consequently, all algorithms using this enigma are though to be in P.
In reallity, the enigma is not touched at all. When an algorithm is improved, we generally think of a way to work around the hard parts. In case of NP to P, this means bypassing the enigma.
Therefore, a solution like the solution to the context-free parsing problem has no effect at all on other problems! Although the invention is a great achievement and although we are stunned afterwards by the simplicity of the solution we could not think of earlier, it usually has only limited effect on related problems. At best, an unrelated problem can be translated to the solved problem and then be otimized as well.
Therefore, it is unlikely that solving the translation from an NP problem into a P algorithm will change the way we think of computational complexities in a revolutionary way.
Every student, after going to classes about NP complete problems, wakes up in the middle of the night one day, and thinks: "I've solved the P = NP problem! I can solve NP problem suchandsuch in P time!". I have.
The general pattern is, that this is simply not true.
Note that it's possible to solve NP complete problems in P time using Exponential space. Don't fall for that trap.
The "proof in the pudding is in the eating". Try to write a program that will implement your algorithm. You will quickly find the loop that takes exponential time....
Roger.
That's wrong on several counts. First, the worst case performance of an algorithm may not matter at all because the worst case is rare or because good randomized versions are available. Second, the constants on the asymptotically more efficient algorithm may be so much worse that it doesn't matter for problem sizes that occur in practice. You see, "N" isn't usually some kind of bragging factor, it corresponds to real-world entities, like people, components, cars, etc., of which there is a bounded number.
While occasionally theoretically interesting, many recently developed algorithms for solving common problems with slightly better asymptotic worst-case complexity are completely useless in practice.
Furthermore, for real problems, "N" often corresponds to real-world objects and doesn't get arbitrarily large, so the relevance of asymptotic results breaks down at some point: algorithms with worse asymptotic complexity may perform better in practice on all problems you would be interested in. This is probably rather the norm than the exception, although people often don't realize it.
So, if P=NP, that would tell you that a large number of problems don't necessarily require exponential time to solve in the worst case. But that doesn't make such problems easy. Conversely, many problems that are NP-hard have, in fact, good, practical solutions in many cases no matter whether P=NP or not (as some cryptographers had to discover to their dismay).
A problem is NP-complete if it is NP-hard and in NP. A problem is in NP if a guess of the answer can be checked in polynomial time. A problem is NP-hard if being able to solve it in polytime means being able to solve any problem in NP in polytime. To prove P=NP, it is sufficient to find a polytime algorithm for an NP-hard problem. (I believe I have seen a result that suggests that there cannot be a non-constructive proof that P=NP, but I can't offer a reference offhand.)
As other posters have pointed out, "in polytime" is not a panacea: the polynomial might be unbelievably bad, the memory requirements of the algorithm might be unreasonably large, etc. (But n^3 is way better than 2^n even for large n: do the math.) There is a belief in the business known as the Polynomial Thesis which suggests that anytime there's a polynomial algorithm, there's a low-order polynomial algorithm.
All the encryption schemes you have ever heard of are in NP: if you can guess the key, you can quickly check that it works. This is true for both private key schemes (trivially) and public key schemes (guess the factorization of the product of two large primes, and you can certainly check it quickly by multiplication). The crypto arms race would then turn to algorithms that use the power of the NP-solver to encrypt: there are results that suggest that this is possible.
Most practical problems which are compute-bound are in NP, and thus tractable for an NP-solver. This includes such things as production scheduling and many kinds of gene and protein sequencing and folding. A few practical problems are believed or known not to be in NP, such as general-purpose planning (PSPACE complete) and checking computer programs for infinite loops (semi-decidable).
Hope this helps. For more information, check out the classic book by Garey and Johnson.
Someone should start a distibuted.net style project to enumerate turing machines until we find a polynomial time algorithm for an NP-complete problem.
If it's possible, we'd find out sooner or later.
Actually, maybe we should devise a system than can enumerate all possible mathematic proofs. Then if P=NP is either provable or disprovable, we'd eventually find out.
(I'm kidding, BTW...)
By the way, nothing prevents a proof that NP-Complete can be solved in polyminial time, but doesn't provide any way of doing so.
Kjella
Live today, because you never know what tomorrow brings
I solved it! I solved it!
I have the proof right here! I'm going to post it right now, right here on Slashdot!
Oh wait, there's a knock at my door. Hang in there folks, I'll be right back...
Muffled Yell
Thud
Long Silence
intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it
After reading a few posts, I realized many others had the same misconception I had until recently. If a problem is NP that does not mean it is not solvable in polynomial time. NP stands for nondeterministic polynomial, and P is a subset of NP.
Very Good sci fi short story. I can't give away the end, but it starts with an NP reduction posted to usenet and things go in some very unexpected directions from there.
8 5
8 5
short story "Antibodies," by Charles Stross
(c) 2000 by _Interzone_.
First published by _Interzone_, July 2000.
Reprinted in 18th annual year's best sci fi
(ed Gardner Dozois) ISBN = 0312274785
more info at amazon
http://www.amazon.com/exec/obidos/ASIN/03122747
but buy it from alldirect for better price
http://www.alldirect.com/book.asp?isbn=03122747
or pick it up and read at you local bookstore.
-matt
It seems impossible, but if you study AI a bit, you'll see that this is what NP=P implies, despite the seemingly enormous search space required by BFS, since chess is NPC.
... such that white wins". You can express all quantified boolean formulas (QSAT) in that form, and QSAT is PSPACE-complete.
Chess NP-complete? Are you sure of that? Are you really, really sure of that? I would like to have a reference to the proof since that statement is VERY surprising.
First, since the rules of Chess are tailored for a fixed 8 x 8 board, it is quite obviously a O(1)-problem (though for a relatively large value of '1').
Second, if we start to vary the size of the board to n x n, my guess would be that we would end with a PSPACE-hard problem (possibly even PSPACE-complete, but quite probably up, up, and away from even that). This is because that the problem is then of the form: "does there exist a white move such that for all black moves there exists a white move such that for all black moves
Note for those that don't know much complexity theory: PSPACE is the class where a problem can be solved using a polynomial amount of space but time is not limited (except that there is at most exponential amount of different computation states). NP is a subclass of PSPACE and it isn't known whether it is a proper subclass or not. However, NP=PSPACE is a very unlikely proposition.
You know what? You're right. It is PSPACE. I'm totally wrong. Thanks for the correction.
Mod me down and I will become more powerful than you can possibly imagine!
It seems to me that if you can solve this problem
in O(n) time then it wasn't NP-complete to begin
with. We shouldn't call things NP-complete unless
we can prove they are.
"The last thing I want to do is deal with a bunch of people who want something."
Major Major
...I meant that the problem in question, originally believed to be NP-complete, would turn out NOT to have been NP-complete, and that therefore any conclusions about NP=P in this case were wrong/irrelevant. This result would therefore not have significant theoretical repercussions, but it might have practical implications, if that problem's putative NP-completeness had led people to believe that a linear-time solution to the problem was unlikely. Suddenly a computational barrier is removed. I'd agree it seems more unlikely that we have a systematic misunderstanding about NP-complete problems and that NP=P. (But of course that's the kind of thinking that was rocked in 1931 by Kurt Godel.)
-- We all have enough strength to endure the misfortunes of other people. La Rochefoucauld
My brother fund a algoritme which solved
the sat problem in o(n^6) time but the
only problem where that it used O(p^n) in space.
Damn, I don't have the time to read all these post, but just reading the topic make me too excited. I know a guy who secretly find an "answer" for TSP (Traveling Salesman Problem). It mean that he can resolve NP Complete Problems!!! He's been working with TSP for more than 30 years but he is too scared to reveal to the public the key of this stubborn problem... He's been keeping this secret for too long... I bet you don't believe me, but thats your problem... btw, I bet my neck that what I'm saying is true... I'm serious, as serius as I just subscribe to slashdot just to write this message... ciao.
"There are about 10^120 positions in chess, if I remember correctly. Even if you could solve it, there'd be no possible way to store the answer"
Not quite true; it is likely that the solution could be expressed as an algorithm that would take up much less space than an exhaustive list of state transitions.
For example, if you had a game where the goal was to take turns naming positive integers until someone was forced to name an integer larger than the one their opponent just named (and thus lost), there are an infinite number of states, but the "solution" can be expressed quite simply:
Say "one."
So, at least in this case, the solution is much smaller than the list of all posible cases. I suspect the solution to chess, while much larger than this, is still smaller that you propose.
You're mostly correct. To find the best move at the beginning of a game, for instance, your example is like choosing an opening. You're also right for the endgame. I imagine that in the middlegame, though, if you're not doing an exhaustive search, then you're using a heuristic. I can't say whether a perfect heuristic can be found for chess, but there would probably be a whole lot of exceptions to the "perfect move" generated, which would need to be stored in the heuristic.
So, with your method, there might be no way to store the algorithm to run! On the other hand, maybe the heuristic could fit onto a 1.44 MB floppy disc. But if the search space wasn't full of local maxima, chess wouldn't be such a hard AI problem. So, the only thing that keeps us from finding the right answer might be the high branching factor, which is more related to the number of positions. Just random thoughts.
They who would give up an essential liberty for temporary security, deserve neither liberty or security
if someone uses private non-algoritmically generated keys to encrypt and decrypt, then the communications are probably secure.
If they use synchronized one-time pads then the communications are probably even more secure.
MSBPodcast.com The opinions expressed here are my own. If you don't like 'em... Think up your own stuff.
Additionally, if time was not an issue, you could solve this problem with very little memory using a simple depth-first-search approach. The amount of additional space you would need would simply be the depth of the stack. The depth of the stack is equivalent to the number of moves. The number of moves in a typical game of chess is less than 50, but what's important is that you can bound the number of moves by some constant.
This is blatantly wrong. A DFS (presumably, you mean a minimax search) would need to visit every possible check- or stale- mate from the starting position, in order to assess it. Then, it would work backwards through the entire search space. Just marking nodes as visited would require more memory than the number of atoms in the universe.
To put it in more simple terms, how would your "depth-first-search" know that the first move was correct, without first knowing the opponent made the best first move, and knowing that you made the best second move?
They who would give up an essential liberty for temporary security, deserve neither liberty or security
then N = 1 !
The face of a child can say it all, especially the mouth part of the face.
NP completeness is something that you will come across in many undergraduate CS programs (e.g. Rose-Hulman Institute of Technology, my alma mater) and something you should most definitely come across in any self-respecting masters program for CS.
Once you start to understand NP completeness, you won't write statements such as:
Many NP complete and NP hard problems have approximations that are extremely close to the optimal answer. A solution to an NP complete problem is unlikely. Quantum computing may in fact be able to solve an NP complete problem because it entirely changes the playing field for mathematical calculations - but who knows? We don't have any quantum computers yet that are more than a meager 'proof-of-concept'. Additionally, it has already been discussed that quantum computing would severely impact the longevity of cryptographic algorithms. I imagine researchers are working on quantum-safe cryptographic algorithms as I write this, though I don't know of any off-hand.
In short, NP complete is a difficult concept to even grasp the basic gist of, much less to fully understand and appreciate the magnitude of its implications. If you want to check out something I wrote on the topic for a master's class at DePaul, go here: http://www.webprojkt.com/brice/csc491/
Many people have pointed out that the Traveling Salesman Problem is NP complete, and so showing P = NP could have practical implications for the business world.
What this misses is the idea of approximation algorithms, which has emerged in recent years. The idea is simple: even though finding the optimal solution to a problem is NP-hard, finding a nearly-optimal solution may be easy. For example, finding the shortest path for the salesman might be very difficult, but finding nearly the shortest path isn't.
For the traveling salesman problem in particular, there is a polynomial time approximation scheme. This means that if you want a solution that is within 10% of optimal, you can get it in polynomial time. If you want one within 1% of optimal, you can also get it in polynomial time. In fact, you can approximate the solution as well as you want in polynomial time. The catch is that the degree of the polynomial increases as you demand better approximations. So, as a practical matter, the Traveling Salesman Problem is already solved. (At least for Euclidean spaces.)
Clay Math Institute in Cambridge has a bunch of stuff on P vs. NP. Here is the link to their site about it. Proving (or disproving) this one gets you a million bucks.
If the NP parts of some crypto are still high order plynominal, no problem arises in practice. If e.g. a one-way function has a complexity of
n in one direction and n^30 in the other it is secure for pretty small values of n. I always wonderd about the "exponential" requirement for these things. Of course it does solve the problem, but high order polynomial against low order polynomial does the job as well.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted and ignored otherwise.
The example of chess you give is surprising. It isn't clear that chess (or any game, for that matter) is obviously NP. If someone gave you "the best move" for white, how would you verify in polynomial time that he is correct? (Note: this assumes an nxn version of chess, since for the 8x8 version, one can just precompute everything: theoretically speaking, 8x8 chess is solvable in constant time).
Search problems are not necessarily NP.
... because if I can come up with it you can be damn sure that someone else already has....and they might not be quite so scrupulious as I am.
People would need to be warned.
To expand on this, I would say that if NP-complete problems were solved, we would quickly find PRACTICAL ways of using quantum mechanics to do cryptography. We already have it in labs (see this link). But I believe research would be more focused as Quantum computation would become necessary.
I don't think there will ever be an end to the problems we have to solve. There will always be one class of problems that are unsolved.
if you had a solution to the P=NP problem which states that P does in fact equal NP, no one would listen. You would be blacklisted from the entire scientific community as a lunatic. Too many important, "smart", and "credible" people have built up entire careers (Sanjiv Aurora, for instance), based on the fact that P does not equal NP. IF you told them they were wrong, well that is like saying the sun does not revolve around the earth. preposterous! no way! end of story, for a couple of decades at the least.
ROT13 !!!!
Hey if the DMCA says it's crypto....
This is not a political statement. This is not legal advice. It's a frick'n Slasdot post. However: I'm Running For
...that I've stumbled across a NP-complete problem the solution to which will allow me to rule the known universe.
I'm not revealing it here, of course, because I don't trust everyone who reads this. (And I have very little desire to be ruled by someone else, especially if they stole the idea from me.)
I doubt this is the only such problem, so everyone should be very careful about publishing any solution.
Eternal vigilance only works if you look in every direction.
It's possible to map single bits of A and B to boolean variables (asume they are N-bit long), multiplication is equivalent o a logic circuit N^2 big, and the problem of finding a solution to a logic circut, i.e CIRCUIT-SAT is NP-complete; which roughly means that factoring is NP.
:).
Most numerical problems are, so that's nothing new.
If one could find a solution, it's easy to demonstrate that it is working, for example by solving all contests driven by RSA. One does not need to actually reveal the algorithm, to prove that he has found it. (At least until appropriate government officials find him
It's bit harder to demonstrate that one actually found that P=NP, but if anyone said that he(she) broke RSA this way, i'd believe the other solution exists, too.
Symmetric cryptography is generally better in this situation, you don't have a 'public' key around so it is not possible to determine in polynomial time if the decrypted data is correct, so the brilliant solution won't help here. Of course if the encryption algorithm adds some checksums or has constant elements, or you had encrypted some plain text with a simple block algorithm, it might be easier (usual cryptoanalysis methods may be applied).
But, there is a greater problem that 'what if somebody finds it out and tells everybody?' - simply replace 'every' with 'no'.
--
#sp
Signature under konstruktion.
I have this proved, I just don't have enough room here to write it out...
-- Is "Sig" copyrighted by www.sig.com?
Publish it to get money? I'd crack electronic money transfers, and make much, much more money than if I had published.
Damn... why does everyone have to go and think inside the box? (the box, in this case being legality and possibly, morality)
-------
Incite and flee.
Let's get the definitions straight first.
1. A problem is in the class NP if it can be solved (or "decided") by a nondeterministic Turing machine in polynomial time. (Nondeterministic is the "N" in NP).
2. A problem P is NP-Hard (or "hard for NP") if, for all problems Q in NP, there exists a transformation T(q) with the followin properties:
o T(q) takes instance q of Q and converts it, in polynomial time, into an instance p of problem P
o for all such q and p, p is accepted (returns solution yes or no) by P if and only if q is accepted by Q.
In other words, given an black box P that decides some NP-hard problem, we can build a box P' that decides all problems in Q.
3. A problem is NP-complete if and only if it is in NP and it is hard for NP (NP-hard).
Why is this of any importance?
Well, problems such as finding primes, factoring large integers, and so forth, are trivially problems in NP. They are no know, however, to be NP-hard (and thus NP-complete). In fact, there is a class of problems lovingly referred to as "NP Incomplete". These problems are really useful to solve, they defy many of the traditional estimation strategies for quickly solving other NP-hard problems, and they turn out to be REALLY difficult to solve, i.e., they are almost always exponential.
There is stong evidence that these problems are NOT NP-hard; they lack a certain expressiveness available in, say 3-SAT or HAMPATH.
So, I say, yes, in the highly unlikely event that someone finds an O(n^k) (for some constant integer k) solution to an NP-Hard problem, much of modern cryptography will collapse onto its left ear. Finding primes, factoring large numbers, all these kinds of tasks would be "effifient".
There are also some more important theoretical consequences to P==NP; with P==NP, several of the time/space (computer science meaning, you phyiscs freaks!) hierarchies collapse, making other, far more difficult problems, tractable.
These consequence of P==NP add to the mounds of evidence that P!=NP -- the consequence would not make sense in may cases.
Either that, or a couple centuries of the most brilliant minds in Mathematics have missed some really simple insights.
Ooh, this is fun stuff to wrap your brain around
-- Alex Blate, blate@cs.unc.edu
You have missed the point. Using a depth-first-seach approach allows you to avoid exactly what it is that you have described.
You sound rather dogmatic, so perhaps it would be instructive for you first to realize that you are wrong: it does not require more memory than the number of atoms in the universe to calculate this answer. The fact that "NxN chess" is in PSPACE stands in direct contradiction to your statement.
"The only rights you have are the rights you are willing to fight for."
I believe a more correct statement is that
real molecular dynamics simulation is in NP, not just proteins (doesn't this boil down to the fact that it is an N-body problem?)?
There are all sorts of ways you can try to fold a protien without molecular dynamics (like homology)...
You have missed the point. Using a depth-first-seach approach allows you to avoid exactly what it is that you have described.
You sound rather dogmatic, so perhaps it would be instructive for you first to realize that you are wrong: it does not require more memory than the number of atoms in the universe to calculate this answer. The fact that "NxN chess" is in PSPACE stands in direct contradiction to your statement.
BULLSHIT. What the hell do you think you are searching? The NXN chess proof doesn't make it implementable. Tell me what structure you are searching. Your first post said you needed a stack of depth 50. This is utter nonsense because in a DFS of a graph, you must keep a list of visited nodes. Otherwise, your super chess program will run in circles until the end of time. Once you keep a list of states, you're screwed for storage space.
My quick search on the internet seems to say that NxN chess is EXPTIME-complete. Even if I give you the right answer for the best move in a particular position, you can't verify it in poly time. This gives more credence to the storage space problem.
They who would give up an essential liberty for temporary security, deserve neither liberty or security
(quote) Is the human brain capable of solving NP-complete problems? That doesn't sound right. (end quote)
I believe that the brain uses close-enuf approximations. Otherwise coffee and Marijuana would turn us into pure blobs (instead of partial blobs).
I believe Penrose (is that the guy?) made a similar mistake when prophezing that the human brain could never be emulated. He was falsely assuming that a perfect simulation of every atom would be needed.
99% may be sufficent to make it functionable. Neural nets are famous for not needing perfect inputs (or perfect connections).
Table-ized A.I.
There are two issues:
- Is NxN chess in PSPACE-complete or EXPTIME-complete?
- Can you compute perfect chess (regular 8x8) in a reasonable amount of space?
Let's look at issue (1) first.Perhaps you are referring to the proof contained in:
Nice catch. Here's the scoop on NxN chess and PSPACE vs. EXPTIME:
If you bound the allowed length of an NxN chess game to be polynomial in N (which is my operating assumption), then NxN chess is in PSPACE (and thus in PSPACE-complete). If, however, you decide to generalize chess into NxN chess so as to allow a less restrictive bound on the length of a game as Fraenkel and Lichtenstein did, you arrive at their solution of EXPTIME-complete.
So this issue is not as clear-cut as I originally thought. Whether one classifies NxN chess as PSPACE-complete or EXPTIME-complete depends on which chess rulebook you decide to follow (note there are several rules which concern when the game is a draw depending on cycles or lack of progress), and how you decide to generalize the game of chess to an NxN board.
However, what's important to note is that it's the actual length of the game that becomes the space issue, not the breadth of the search space.
With that in mind, let's hit issue (2):
So it sounds like you understand minimax searches, etc., but perhaps you are not use to thinking in the completely frightening way that you need to think to solve PSPACE proofs. Don't think about issues like maintaining a visited list to help speed efficiency. We can visit the same state over and over again, as long as we don't cycle repeatedly, thus leading to an unbounded game length. And we know if we are cycling since we store the stack of moves we have made corresponding to the current branch.
Fundamentally, white needs to determine if there exists a move1 that for all black move2s there exists a white move3 such that for all black move4s, ..., there exists a white moveN such that white wins.
Well, let's say that we're on move12 for some assignment of move1, ..., move11, and we see that black wins. What this means is that we go back to move11 and say, ok, that is not a move that is going to cut it since it doesn't work for all black moves from that state. Let's try "the next" move11. Let's say that after trying every move11 we didn't find anything that lead to victory. Ok, that means that black's move10 was a good move for black and we can't allow black to get to this position, so we need to go back to move8 and pick the "next move", etc.
And you can envision that the "next move" is simply an operation that is performed on a chess state which ultimately generates an iteration over valid chess moves from that state.
So now the question is, what is the maximum number of moves in a (regular) game of chess? Typically it's about 50, but let's bound it by 1,000,000,000 just to be obnoxiously unrestrictive. Ok, how much space does each state require? Let's say about 1K. So we need to be able to store 1 Terabyte of data. No problem.
"The only rights you have are the rights you are willing to fight for."
The O(n lg n) algorithm you invented? It's been a while since I've looked at this stuff, but I seem to remember that there were at least two O(n lg n) algorithms for computing a Delaunay triangulation (Fortune and Guibas-Stolfi). You are talking about planar triangulations, correct?
Reuven
The usual workaround is approximation.
Right, and approximation is almost always good enough.
Consider the kind of optimizations that are usually tackled by the simplex method, such as how much of each size shoe or model of computer to make so that you optimize your profits. The simplex method, worst case, is NP. Back in the 1980's, someone in the Soviet Union came up with a guaranteed P solution to those problems which I only vaguely remember (it involved ellipsoids, but that's all I can recall). Did everyone immediately switch? No, because
So, basically, the simplex method is plenty good enough, so people use it. The same is true of others. There are node-visiting problems that are NP, but you can get very close to optimal with simuated annealing or genetic algorithms, which are simple and converge quickly. Is it really worth saving a teacup of fuel by finding an exact solution, which will be way less than how much variation you get from delays on the taxiway?
It is really nice to have an exact, provable solution to a problem from an aesthetic standpoint. However, a solution that works in practice is usually all that is necessary.
As others have pointed out, factoring large numbers isn't even NP in the first place; it's just way harder than constructing two large primes. Even that is due to an approximation, an algorithm that tells you if a number is probably prime.
So, what would happen? We hard-core CS types would be ecstatic, but the rest of the world would mostly just shrug.
Well, let's say that we're on move12 for some assignment of move1, ..., move11, and we see that black wins. What this means is that we go back to move11 and say, ok, that is not a move that is going to cut it since it doesn't work for all black moves from that state. Let's try "the next" move11. Let's say that after trying every move11 we didn't find anything that lead to victory. Ok, that means that black's move10 was a good move for black and we can't allow black to get to this position, so we need to go back to move8 and pick the "next move", etc.
I'm not sure we're talking about the same problem. NxN chess, if I understand it, tries to find a guaranteed win from a specific position. From the opening position on a real chess board, there is almost certainly no strategy to guarantee victory for white or black. If there was a sequence of moves such that for every black move, white can find a victory, then I might understand what you are saying, but in chess, there is no such sequence. There may be a "best" move in any position for either side, but there is no guaranteed win from the start. Does this make sense?
They who would give up an essential liberty for temporary security, deserve neither liberty or security
Right on. But notice that a specific position is the starting position.
Actually, nobody knows the answer to this because nobody is able to calculate it. There are only three posibilities in the game of chess:
- White can always win.
- Black can always win.
- White and Black can always force a draw.
What continues to make chess an interesting game is that it's complex enough for a human not to be able to plan ahead and always know what to do.In this context, chess and tic-tac-toe are very similar games. Each player makes a move until one player wins or it is a draw. The difference is that tic-tac-toe is simple enough that it is relatively easy to calculate the "best" move.
There is no luck in chess. There is a "best" first move, but calculating it is a major challenge.
"The only rights you have are the rights you are willing to fight for."
This lecture note for my Computability class simplifies the problem to terms that people can understand. This is a definitely good read if you're interested in P vs NP
_______________________________
"I'm not Conceited...I'm just a realist..."
QUANTUM LEAP FOR QUANTUM COMPUTINGm l? tag=mn_hd
IBM researchers announced they have used a newly developed computer to
perform "the most complex quantum computation to date" in a demonstration
of "Shor's Algorithm," a method of factoring numbers that was developed in
1994 by AT&T scientist Peter Shor. IBM's new quantum computer is based on
seven atoms that comprise both the computer's processor and memory.
Previously, the most powerful quantum computer developed by IBM was based
on five atoms. In the most recent demonstration, the tiny computer was able
to correctly identify 3 and 5 as the factors of 15. "Although the answer
may appear to be trivial, the unprecedented control required during the
calculation made this the most complex quantum computation performed to
date," said Nabil Amer, a manager at IBM's Almaden Research Center. The
research is still at a very early stage, but could eventually have an
important impact on cryptography, since many of the mathematical techniques
used to encrypt digital information rely on the idea that it is at present
almost impossible to factor large numbers. (Reuters/CNet.com 19 Dec 2001)
http://news.cnet.com/news/0-1003-200-8234595.ht