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.

Comments

RSA and all would *not* die

[JF]

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. :)

Re:*sigh*

[quokka70]

>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).

There are simple functions f(x), for appropriate definitions of "simple". Here is one.

Define the constant A by:

A = \sum_1^\Infty (p_n / 10^(t_n))

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

f(n) = floor(10^(T_n) * A)

where floor is the integer part truncation of the argument, and T_n is the sum of the first n triangular numbers:

T_n = 1 + 3 + 6 + ... + t_n

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.

Check your theory

[OeLeWaPpErKe]

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.

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 ... you can destroy public key encryption in a simpler way ...

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 ... "Fundamenten van de informatica" by B.Demoen

Re:Only the PK crypto

[Dr. Blue]

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!