Consequences of a Solution to NP Complete Problems? 525
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.
Salesman (Score:4, Funny)
NP is Optimization (Score:5, Informative)
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.
Re:NP is Optimization (Score:4, Informative)
shortest-path on a graph
matrix chain multiplication
polygon triangulation
Huffman encoding
I could go on, but I won't.
GS
Unseen consequences! (Score:3, Funny)
sa? (Score:2)
AI (Score:3, Insightful)
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.
Re:AI (Score:2)
Re:AI (Score:2, Informative)
Not necessarily true. Remember, NP-complete means all NP problems can be reduced to it in polynomial time. So even if I found a O(n) solution to, say, Hamiltonian Path, it's quite possible that reducing (say) Traveling Salesman to Hamiltonian Path is not a linear-time reduction. It might be any polynomial, maybe n^5. In fact, the degree of the polynomial might depend on the kind of computer you have at hand (for instance, whether you have a random-access memory where you can access any word in constant time, or a tape where you have to wind through the whole thing to find the word you want.)
Re:AI (Score:2, Funny)
Who gives a shit, cockgoblin? A problem in polynomial, n>=2, time is not solvable in linear time, which is what the original poster was claimimg.
Discussing cockgoblins and polynomial equations in the same post makes my day. Thanks for the smile.
Is "harvardian" from Harvard? What does he know anyways..
Re:AI (Score:2, Insightful)
I assumed he meant that an O(n^t) solution with a very large value for t would be of theoretical interest but not have the kind of practical impact that he was thinking of. In other words, he meant O(n) or at least a relatively tractable O(n^t).
In essence you're right, an algo with a huge t would not be all that practical. However, once you have it down to poly time, it becomes relatively easy to get it into a more usable time space. I remember a lot of things from my datastructures class where the obvious solution was quadratic, with a little tweaking you got linear, and with some very convoluted code you got N/2 or better. I am not sure what that problem was (it may have been sorting), but that type of problem is pretty common. Despite that, for large problem spaces, the poly-time algo will be better than the exp-time algo.
Re:AI (Score:2, Informative)
O(n) *means* linear time.
The actual quest is to prove that P=NP (or that P != NP), meaning any/all NP problems can be solved in O(P) where P represents any polynomial equation. Not O(n), whatever the article may say.
-Graham
err... what do you think? (Score:3, Funny)
Publish it as soon as possible, get credit for it, and rack up the monetary prize, don't you think?
Re:err... what do you think? (Score:3, Funny)
I'd memorize it and then try to figure out how the guy did it
Only the PK crypto (Score:5, Insightful)
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.
Re:Only the PK crypto (Score:2)
Re:Only the PK crypto (Score:2)
Re:Only the PK crypto (Score:2)
Either way P=NP doesnt seem to imply that there are no aysmetric function...just that there are no aysmetric polynomial time functions. There seems to be no theoretical reason why you couldn't build a PK system with an exponential encryption time and a super super exponential decryption time.
Secondly I am unsure if it even gets ride of polynomial time aysmetric functions. It puts a bound on how aysmetric they can be...as to whether this will mean a practical inability to do PK I don't know
Re:Only the PK crypto (Score:2, Informative)
Re:Only the PK crypto (Score:5, Informative)
Re:Only the PK crypto (Score:2)
Re:Only the PK crypto (Score:2, Insightful)
Factoring is not known to be in NP or NP-complete
Re:Only the PK crypto (Score:4, Interesting)
First, to all the people who keep saying "factoring isn't NP-complete" blah, blah, blah. That's not even a sensible question, since "factoring" isn't a decision problem. However, you *can* define a related decision problem that shows that if P=NP, then you can factor in polynomial time. So if indeed someone came up with an O(n) time algorithm for an NP-complete problem, then factoring would definitely be doable in polynomial time, and unless this were some really bizarre problem then factoring would most likely be pretty easy.
Second, factoring isn't the only thing that's affected here. If all problems in NP are efficiently solvable, then *all* cryptographic algorithms (public key or symmetric) are susceptible to known-plaintext attack. Meaning, if you know a plaintext and corresponding ciphertext, you can find the decryption key --- since that's always trivial to do with a public key algorithm (since you can create the ciphertext yourself), they'd all be easy to break.
So yes, public key crypto would cease to exist as we know it --- the only hope would be to find a function that's maybe O(n) to encrypt and Omega(n^10) to break, but an exponential time separation wouldn't be possible any more.
But symmetric key crypto would also be severely damaged as well.
Fortunately, most people think this is pretty unlikely!
Re:Only the PK crypto (Score:3, Insightful)
But the future of cryptography would be seriously shaken, since technology gets better and better, eventually the asymptotically faster methods will become the best way to do things. If the asymptotically fastest method is polynomial, then key lengths will have to get bigger faster and faster. Currently, increasing your key size by a X bits per year makes you immune to attack. But if there is a polynomial time attack, then suddenly the key size has to grow exponentially. Imagine doubling your key size every month.
I believe all cryptographic schemes are based on algorithms that are NP. Being NP means that the solution can be verified in polynomial time, but the solution cannot necessarily be found in polynomial time. The verification part is important to cryptography, since you have to be able to prove to other people that you can solve the problem (since you have the key).
I challenge anyone to name a cryptosystem that is not based on a problem that is NP.
If I had that O(n) algorithm... (Score:3, Offtopic)
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.
Re:If I had that O(n) algorithm... (Score:2)
A certain P solution can be proven to always find a path at most twice the length of the optimal one.
Crypto is safe (Score:4, Informative)
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.
Re:Crypto is safe (Score:2)
(Nater pulls head out of ass, puts foot in mouth)
That should say "factoring large numbers" rather than "factoring primes"
My bad
Re:Crypto is safe (Score:3, Informative)
I'm familiar with several fast primality testers, all probabilistic, but I'm not familiar with any fast factorization algorithm.
Re:Crypto is safe (Score:2, Informative)
Re:Crypto is safe (Score:2, Redundant)
Oh, it's certainly not difficult. I can factor primes in O(1) time. Give me any prime and I'll tell you all its factors. However, the only known algorigthm to factor non-primes runs in exponential time. You got to love it when a clueless post gets marked "insightful" by even more clueless moderators.
Re:Crypto is safe (Score:4, Funny)
Oh yeah? I've got a nifty little program right here that will factor your large primes in O(1)! Don't believe me? Read it and weep!
int factor(int largePrime)
{
return largePrime;
}
Re:Crypto is safe (Score:2, Informative)
Are you on drugs? Most canonical methods of generating One Time Pads are based on physical processes, like throwing dice, sampling a radioactive source or [berkeley.edu] digitizing lava lamps [lavarand.com]
Using a pseudo-random generator to generate one time pads offers pseudo security.
Re:Crypto is safe (Score:3, Informative)
You're mixing things up. One-Time Pads are simply long strings of random numbers, you don't use Diffie-Hellman to generate them. And if you used DH to exchange them you defeat the point (which is that they're provably secure). They're generally delivered by trusted courier. OTPs are used (for instance) for some sensitive communications with US embassies and presumably by the CIA and NSA as well.
DH is completely unrelated to one time pads.
Sumner
Pizza and UPS Packages Would Arrive Faster (Score:4, Funny)
I would really hate that! (Score:4, Funny)
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.
Re:I would really hate that! (Score:4, Funny)
Re:I would really hate that! (Score:2)
An alternative method is to live close, but have an address that's just really hard to find: growing up I lived in a city that had a pretty consistant grid layout to the streets, at least in any part of the city that was more than 15 years old. We lived on this little street that curved right through a couple of these otherwise nice rectangular blocks. I think it was all the free pizzas we got that caused Domino's to change their 30-minutes or free policy - the complaints about reckless driving were just a red anchovie.
The name of the court I live on now is shared with the attached street, an avenue, and a boulivard (sp?) located in rather different parts of town. Since none of the pizza joints here have a 30-minutes or free policy, I just always pick up the pie because otherwise it takes about 2 hours and 3 phone calls for them to find us.
The moral to the story is that a linear (or even polynomial) solution to the TSP is not going to keep the pizza places from giving you free pies as long as you live somewhere that either causes the algorithm to bomb (like next to a circle that causes the program to get caught in an infinite loop), or at an ambiguous address.
-"Zow"
Re:Pizza and UPS Packages Would Arrive Faster (Score:2)
It's even less important than that. (Score:3, Insightful)
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.
Re:Pizza and UPS Packages Would Arrive Faster (Score:2)
I pity the poor pizza boy who not only has to deliver pizzas to the entire United States, but maybe also has to wait for an O(google) (but not NP - whoopee!) algorithm to calculate his route before he can even start!
:-)
Re:Pizza and UPS Packages Would Arrive Faster (Score:2)
N^1000 vs 100 * N^10 looks like a no brainer to me!
Now of course it's not optimal, but with a not too big, not too small grid it's going to be good enough, and if you can assign 10x10 pizza boys to the job they'll probably be done before the lone pizza delivery boy has even submitted the job to distributed.net
I'll give you the O(google) multiple snafu though!
With such an algorithm I would (Score:2, Insightful)
P=NP doesn't mean O(N) (Score:4, Informative)
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
Decryption not NP-Complete, Implications of Poly (Score:4, Insightful)
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.
Re:Decryption not NP-Complete, Implications of Pol (Score:2)
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?
Re:Decryption not NP-Complete, Implications of Pol (Score:2)
Re:Decryption not NP-Complete, Implications of Pol (Score:2)
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
Like I said (Score:2)
All NP-complete problems can be considered search problems. All search problems can be parallelized.
O(n^x) is not necessarily hard... (Score:3, Insightful)
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.
Ahem... (Score:3, Insightful)
As an aside, when did slashdot become a meta-search engine? Oh wait... never mind!
Here's a news flash (Score:2)
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.
The obvious answer.. (Score:3, Funny)
RSA and all would *not* die (Score:4, Interesting)
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.
Mixed up... (Score:3, Informative)
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
You're a little confused.... (Score:3, Informative)
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
Re:You're a little confused.... (Score:3, Insightful)
I can't comment on the math in the second half of your posting but your definition of NP-complete is wrong on many levels.
First of all, it isn't known whether NP is equal to P or not, so its nto safe to say that there is no O(n^k) solution to those problems. This is minor because it is widely believed that P!=NP.
Second, NP is a superset of P. That means all the problems in P are also in NP!
Third, your definition is wrong. NP is the group of problems that can be solved by a nondeterministic turing machine in polynomial time. If you don't know what this means, there are several good books out there. Come back to this post when you have read them.
Fourth, it hasn't been shown that there are ANY problems in NP, but not in P, but aren't NP-complete! That means all the so-called NP (excluding P here) problems we know of are NP-complete! Now they may be some that lie "between NP-complete and P but no one has found one yet. Or proven that a problem we know of lives in this set.
Lastly, there are harder problems than NP-complete problems. See PSPACE and EXPTIME.
Re:You're a little confused.... (Score:2, Informative)
That's not true. Factoring and discrete log are NP but not shown to be NP-complete. It is relatively easy to show that some problem is in NP (If you can check an answer for validity in polynomial time it is in NP). Much harder to show that it is NP-complete (Need to show that the SAT problem can be solved in poly time if the given problem can be solved in poly time).
On another note, quantum computers can solve factoring and discrete log in poly time thus breaking most cryptosystems. However, it is believed that quantum computers will not be able to solve NP-complete problems in polynomial time.
An interesting question is that if P!=NP then are there some problems that are not in P and not in NP-complete. The answer is not known but factoring could be a candidate.
you too (Score:5, Insightful)
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)
Re:what about normal 128 bit encription (Score:2)
Symmetric crypto is already considered to be stronger than the available public-key methods. Well, stronger may be the wrong word: better studied and less likely to fall to a sudden advance in mathematics.
Most systems that use public key crypto (including e.g. PGP, ssh, ssl, all of which use RSA most commonly) use the public key method only to exchange a key and then use that key with a symmetric algorithm (most widely 3DES (SSH), IDEA (PGP), and RC4 (SSL), but plenty of others are common)
This approach limits the amount of crypto text (and known plaintext) available to attack the PK system with.
Sumner
If I solved it... (Score:2, Funny)
"Oh, and by the way, here's the solution to some NP complete problem..."
NP is not O(n) (Score:2, Informative)
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...
Understand NP-completeness, please (Score:2, Informative)
What? (Score:2)
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
Misconceptions (Score:4, Informative)
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.
More good things (Score:4, Informative)
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.
Factoring is NP hard (Score:2, Insightful)
Even if P == NP, not out of the woods yet (Score:3, Informative)
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!
The answer is clear.... (Score:4, Funny)
Check your theory (Score:2, Interesting)
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
NP Complete is NP Complete (Score:2)
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.
A slide from class (Score:3, Insightful)
"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).
It'd be awesome! (Score:2)
:-)~
A more interesting question (Score:2)
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).
Somebody? (Score:2)
I'll give you a cookie if you do, and undoubtably you'll get a +5 Informative.
You're All Bloody Wrong (Score:4, Informative)
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).
Clarification (Score:2)
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....
Answering the actual question (Score:5, Insightful)
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
Re:Answering the actual question (Score:3, Insightful)
>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?
The question of whether or not such a world-altering technology would "make it into the wrong hands" is easy to avoid if you get this world-altering technology into *everyone's* hands, all at once.
For example, if you showed someone 50 years ago a PC from nowadays, they'd be like "Oh my god I could take over the world with this thing!" and possibly make a huge fortune. If, however, you gave one computer to every one of the billion people living back then, and showed them exactly how to manufacture more, they'd be like, "Oh, a new, faster, cheaper computer. So what?"
So, if you ever find that P=NP, spam EVERYONE with the solution. That way the "wrong hands" and the "right hands" think its a pretty commonplace thing.
Most block ciphers are no harder than NP-complete (Score:2, Informative)
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
Sci-Fi (Score:2)
I wonder if the poster was 'inspired' by this story?
Take it from a graduate student. (Score:3, Informative)
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...
The real story of P and NP (Score:3, Informative)
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 [fatbrain.com].
I solved it (Score:4, Funny)
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
Re:*sigh* (Score:4, Insightful)
If only it was easy to find any decimal of PI with a simple formula, [blah blah]
Well, it almost is. [slashdot.org] Not decimal, precisely, but any arbitrary hex digit...
Re:*sigh* (Score:2)
Re:*sigh* (Score:2, Informative)
Re:*sigh* (Score:2, Informative)
As any chemistry class can tell you, this is practically impossible.
>If a person could find an function f(x) that returns the xth prime number, [blah blah]
Actually, you can. Anyone proficient in a programming language can code one easily enough, and anyone with any math experience can write out a description of said function. I think you meant a "simple" function f(x) (i.e., non-recursive), which I think has been proven impossible (although don't take my word for it).
>If only it was easy to find any decimal of PI with a simple formula, [blah blah]
It is. See other replies to your post.
>"If a person were to find a O(n) solution to an NP complete problem [blah blah]"
What's so different about this question? It's still open! All the examples you posted are either solved or proven unsolvable. This question is neither.
Re:*sigh* (Score:2, Interesting)
There are simple functions f(x), for appropriate definitions of "simple". Here is one.
Define the constant A by:
where \sum denotes summation, p_n is the n-th prime, and t_n is the n-th triangular number. Then A = 0.2030050011... In particular, A is a constant, and so "simple". Now define the function
where floor is the integer part truncation of the argument, and T_n is the sum of the first n triangular numbers:
Then, up to bone-headed off-by-one type errors on my part, f(n) = p_n.
You may or may not regard this function as "simple". It is almost certainly not useful for generating primes.
It is not hard to show that no non-constant polynomial can take on only prime values as inputs range over the integers. Rather more interestingly, there are (multi-variate) polynomials whose positive values are exactly the primes, but who also take on a bunch of "junk" negative values.
Cheers, quokka.
Re:*sigh* (Score:3, Insightful)
Actually, you can. Anyone proficient in a programming language can code one easily enough, and anyone with any math experience can write out a description of said function. I think you meant a "simple" function f(x) (i.e., non-recursive), which I think has been proven impossible (although don't take my word for it).
Well, if you want to define function in any way you want, then of course, I can find a function which returns the primes. I define f so that f(n) is the nth prime. Woo.
Of course, this function is completely meaningless. The poster was of course saying that it would interesting to find a function which allowed you to compute the nth prime without knowing the primes already. This has not been found. Of course, you can't prove that it's not possible, because our conditions are pretty vague. I mean, there are certainly many smooth functions whose value at n is the nth prime. And for any finite number N, there is even a polynomial whose values at 1,2,...,N are the 1st, 2nd, ... , Nth prime. But unless you could say something about these functions, then they are useless.
For example, there is a function whose value at 0 is the time of my birth,at at 1 is the time of my death. Claiming there is such a function doesn't tell me much.
>If only it was easy to find any decimal of PI with a simple formula, [blah blah]
It is. See other replies to your post.
I was going to reply to this elsewhere, but since I'm already typing...There is a result where one can calculate the nth digit of \pi in hex (and I think in any base which is a power of 2), but, surprisingly, there is no analogous algorithm for base 10. So you might say, well, the hell with it. Just compute the nth digit in hex, and then convert. But, to convert from hex to decimal to find the nth digit, you would need all of the preceding digits. A funny little Catch-22. Although, it's certainly possible that there is an analogous base 10 algorithm, just noone knows it.
No (Score:2)
Re:The Big if (Score:2)
Care to give a reference...... I did a google search on that and came up with nothing...
If you're thinking about 'Fermats Last Theorem', it was solved in 1993/94 by Andrew Wiles.
Oh no! (Score:3, Funny)
'polynomial time' can still be a long-ass time.
Re:Advance in computer science? (Score:5, Informative)
Several router manufacturers are designing their new equipment with support for MPLS. MPLS, among other things, offers better support for traffic engineering. Traffic engineering means deciding which router hops to take to get from border point A to border point B (it also means you can select an alternate route depending on network congestion or backbone router failures).
Finding the most efficient path between the two endpoints is an NP complete problem.
I think this problem also exists for BGP/IGP networks, but I'm not experienced with them. I do know that the promise of the internet being secure and redundant and safe from one node being bombed is a bunch of nonsense. Although the technology to route around outages exists, the chore of houskeeping for it has turned out to be rather intractable so it is minimally implemented at best. Usually if a large backbone provider suffers a hardware failure and can't swap in a backup, they call in one of their router guru's to look at their topology map and configure their other routers to route data around the bad router at that time. That's the automated process.
All the providers out there would *REALLY* like a tool that could take their network topology map and output a reasonable set of LSPs (MPLS tags that indicate the route the packet is to take) for them in a reasonable amount of time. However, since this problem is NP complete, such a tool would have to compute every possible path and then choose those at the top of the list.
Re:Advance in computer science? (Score:5, Funny)
Re:Advance in computer science? (Score:3, Insightful)
huh? dijsktra's algorithm solves the shortest path problem in O(n^2) for the general case, O(n log n) for most real-world problems, in which the graph is sparse.
nobody
Re:Depends *which* NP-Complete problem gets solved (Score:2, Redundant)
Re:Shor's Algorithm (Score:2, Informative)
From the perspective of theorectical computer science this means nothing. NP problems are measured by the speed they run on DETERMINISTIC *turing machines* which means traditional computers and the like. Remember that NP problems can be solved by nondeterministic turing machines in polynomial time. No one cares how long it takes on a quantum computer, because they aren't deterministic turing machines.
And if one NP-complete problem were found to have a polynomial time solution on a deterministic turing machine we could reduce all the other NP-complete problems to this problem in polynomial time and solve them just as fast. This is how one goes about showing a problem is NP-complete
A proof. (Score:3, Informative)
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 [amazon.com] 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.
Re:Not likely to find that P=NP (Score:2)
The writer most likely was thinking of the famous open question, Are there an infinite number of twin primes? Twin primes are pairs of primes whose difference is 2, for example 17 & 19, or 41 & 43. It is conjectured but unproven that the twin primes are inexhaustible.
Re:How to break encryption (Score:2)
On the other hand, you've not really done anything there. All you're roughly saying is, find the greatest common divisor of r and all numbers less than r, which is intuitively even worse than just factoring the damn thing.