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?
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
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.
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
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
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).
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
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
Uh...
If only it was easy to find any decimal of PI with a simple formula, [blah blah]
Well, it almost is. Not decimal, precisely, but any arbitrary hex digit...
sig fault
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.
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.
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
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.
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.
Education is a better safeguard of liberty than a standing army.
Edward Everett (1794 - 1865)
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!
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.
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!
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.
I've discovered a wonderful linear way to calculate optimal routing that I'd like to share, but unfortunately my keyboagu;[f=s af\sdfgsv asdfw352.,.f354asf
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
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).
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
parturiunt montes, nascetur ridiculus mus
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
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).
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.
Come on, give it up, that's
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!
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
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
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...
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.
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