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.
Many real problems that arise in practice are
known to be either NP-complete, or worse, not
computable at all. The usual workaround is
approximation. Compiler writers, to name one
example, will tell you all about it.
So, yes, solving the P=NP? problem in favor of
P=NP! would indeed be a major breakthrough, at
least for some computer scientists.
(Of course, there is no hope regarding the
problems that are not computable. And then
there are problems that are not just NP-complete
but even harder than that. P=NP would not
be the end to all trouble.)
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.
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.
EVERY np complete problem can be mapped on any other (because it can be expressed in a simple logic language, and given one of the solutions you can generate any other by doing math with the solution you have). If you can calculate something that takes infinite processing power, you can calculate any other thing that requires that same amount.
... you can destroy public key encryption in a simpler way ...
...
... "Fundamenten van de informatica" by B.Demoen
The implications would be simple yet brutal, breaking a key of 128 bits would require 128 times the amount of time to break a 1 bit key.
There are still stronger mathematical formulae, but they must have continuous key spaces for encryption to work, if they want to defeat this, in other words, you will not only need an infinite amount of possible keys, but also an infinite amount of keys between any two given keys.
But that's not more than normal
The security of PKE is that you cannot easily determine the exponent of a given number. In other words given a and (a^n mod m), you cannot easily determine n. Right now there are algorithms that only work if n complies with a simple restriction. The alternative to that method is trying everything out. If some smart mind can generalise those algorithms we would have lost encryption as we know it
I only know a dutch text discussing this
tography/page-1.html for more quotations like that:)
rsa is not np-complete, it relies on factoring which is not know (or believed to be np-complete) My professor, the A in RSA, told us this himself.
A few theory things to clear up:
1) Completeness. A polynomial solution to any NP-Complete problem would mean that there would then be a polynomial solution to *all* problems in NP, i.e. that P=NP. This does in fact mean that the usual problems we assume to be superpolynomial for encryption purposes (i.e. factoring, discrete log) would have polynomial solutions, since they are in NP, though not believed to be NP-complete.
To check whether a decision problem is in NP, simply find a polynomial-length "hint" with which you can solve the problem in polynomial time if the answer is yes. For instance, satisfiability is in NP because a satisfying truth assignment allows you to check quite quickly that a formula is satisfiable. Discrete log is also easily seen to have such a hint (i.e. if you're told the discrete log, you can check quite easily that it actually is by exponentiating). Factoring is harder to show in NP, but possible.
2) Complexity measures for numbers. While we usually think of numbers having their own sizes (2 is bigger than 3, etc), when we talk about the inputs to algorithms being numbers, for compleixty purposes, we usually want to think of their size as being their length in binary digits rather than their size, since numbers get harder to deal with for addition, multiplication, etc. as their length increases (adding any two digit numbers is pretty much the same difficulty compared to adding three digit ones). So while we can factor n in time o(\sqrt n) by brute force, we really want to do it in time O((log n)^t) for some constant t. This is what would constitute a polynomial time solution here.
3) Large exponents. It is absolutely true that P=NP would only mean that there was a polynomial solution to factoring; this could still have a huge exponent and still be really slow. But I assume that the original poster was interested in the potential for a fast solution.
Assuming a fast solution to an NP-complete problem, yes, lots of public-key cryptography would break badly (much symmetric key would still be as safe as ever). The responsible thing to do would probably be to announce the solution with some lead time, after making arrangements for your own safety until the solution could be published widely. Though if it were actually satisfiability that we could do quickly, rather than just factoring, there would be lots of other interesting things you could do (solve many engineering optimization problems quickly, for instance, and use computers to prove most mathematical theorems fast...)
I hate to be harsh, but there is some of the most phenomenal crap posted on this story that I've seen on slashdot in a while. This is what I do guys, so let me clear up some things:
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!