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.
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
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.
be the king of MineSweeper
delete free(system.gc);
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.
Clearly, you have no idea what NP-Complete means. NP-Complete problems are problems (technically, languages) that can be used to solve other NP problems, with a polynomial degree of overhead.
As an aside, why do people think that quantum computation somehow lets you break the rules of computation and complexity? Quantum computers are not non-deterministic turing machines. They are not magical. They do not factor numbers in "quadratic time," etc.
Sorry, but I actually took the time to learn this, and I hate it when people just spout of random garbage as if they had a clue.
The ignorance in this thread was just so offensive that I needed to speak up.
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!
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'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..!)
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).
I think you are confused actually.
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.
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
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.
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
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
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.
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.