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

LOL

[Tom7]

If this is a troll, it's a great one. Otherwise, you are an idiot.

Re:Crypto is safe

[jareds]

Yay! I just discovered a new algorithm! Take the number to be factored and call it n. Then, for i=2 to n/2, see if i divides n. This is much faster than exponential time.

When choosing an encoding to map an abstract decision problem to a concrete problem, it is traditional (read: all sane people do this) to represent numbers using a place value system (such as binary) rather than something stupid like unary bit strings. Therefore, the size of the input is Theta(log(k)), if the input is a single number k, so a O(k) solution is O(b^n), where n is the size of the input and b is a constant.

You've got to love it when a clueless poster follows another clueless poster and tries to show how fucking great they are.

You're right, it's quite amusing.

Re:Crypto is safe

[acidblood]

Ok, Mr. Know-it-all. Here's all the evidence I could gather for you. I really don't know why I spent so much time responding to an obvious troll, but it seems the moderators don't agree with me.

I hope that you realize, by the end of this post, that you shouldn't comment on subjects you have no clue about. Even worse, in this case, you have the wrong `clues'. You managed to squeeze a lot of stupid and wrong stuff in a few lines, and you seem to stick to you. So here goes:

factorization is easy

From the RSA Labs Cryptography FAQ (here's a link to this particular question):

Factoring is the underlying, presumably hard problem upon which several public-key cryptosystems are based, including the RSA algorithm. (...) It has not been proven that factoring must be difficult, and there remains a possibility that a quick and easy factoring method might be discovered, though factoring researchers consider this possibility remote.

Oh, then you must be wrong somewhere, OK? I know exactly where. Here's from the book ``Algorithms and Complexity'', by Herbert Wilf:

The problem is this. Let n be a given integer. We want to find out if n is prime. The method that we choose is the following. For each integer m = 2,3, ..., floor(sqrt(n)) we ask if m divides (evenly into) n. If all of the answers are `No,' then we declare n to be a prime number, else it is composite.

OK, so as a primality testing algorithm, it is rather inefficient. The Jacobi sum test and Atkin's test have a much better asymptotic growth, but if you look at it, you can use the same procedure to factor numbers.

We will now look at the computational complexity of this algorithm. That means that we are going to find out how much work is involved in doing the test. For a given integer n the work that we have to do can be measured in units of divisions of a whole number by another whole number. In those units, we obviously will do about sqrt(n) units of work.

See? Your O(n) algorithm (O(n) according to your stupid notation) is already a slow one. There are much faster algorithms out there than trial division. You should be realizing, by now, that you are beyond clueless, but here's the finishing touch:

It seems as though this is a tractable problem, because, after all, n is of polynomial growth in n. For instance, we do less than n units of work, and that's certainly a polynomial in n, isn't it? So, according to our definition of fast and slow algorithms, the distinction was made on the basis of polynomial vs. faster-than-polynomial growth of the work done with the problem size, and therefore this problem must be easy. Right? Well no, not really.

Reference to the distinction between fast and slow methods will show that we have to measure the amount of work done as a function of the number of bits of input to the problem. In this example, n is not the number of bits of input. For instance, if n = 59, we don't need 59 bits to describe n, but only 6. In general, the number of binary digits in the bit string of an integer n is close to (log n)/(log 2).

If we express the amount of work done as a function of B; we find that the complexity of this calculation is approximately 2**(B/2) , and that grows much faster than any polynomial function of B.

Satisfied there? Great. Now, if this book isn't enough for you, go out there and try to find another book which contradicts this one. And no, Teach Yourself Algorithms in 21 days, or something along these lines, doesn't count. Which seems to be your source of information; otherwise you'd have refrained from posting this.

Now, for the really stupid part:

The reason cryptosystems based on factorization are thought to be safe is because we can choose arbitrarily large values of n and we presume that there is no more efficient way to factor integers.

This shows how you have no understanding of asymptotics, or the general field of complexity of algorithms. Refer to the introduction of any good book on the matter, and you'll realize how wrong you are.

If that's not a good example, do some research on calculating Pi, for instance. You'll soon realize that the bottleneck for those computations is a means to do fast multiplication, and it can be done today in better than O(n log n) time (this particular value is the growth for the FFT-based methods.) But still, it can't be done yet in O(n) time, and it has been proven that this O(n) is the theoretical floor for a multiplication algorithm. So, it can't possibly do better than factorization, correct? But how come I can calculate a couple billion digits of Pi on my computer, while I can't factorize even a 100-digit number? In fact, I think I could hardly factorize an 80-digit number in the same amount of time it takes for calculating these billions of digits of Pi. (And it makes sense that algorithms for factorization are researched far more frequently than algorithms for Pi-calculation.)

Now, if you haven't convinced yourself, there's nothing more I can offer. I just hope the moderators read this post and mod you down into -1.

Now, if someone were to find a way to factor integers faster than O(n), we could still keep increasing n but that alone might not be sufficient.

I have shown you one such algorithm above. Did this change the world? No. And it is still a very slow algorithm by today's standards. Oh, and did I mention that it was invented by the greek mathematician Erathostenes, a few millenia ago? You should rethink about posting every idiot idea that comes out of your head from now on; at least avoid a complete embarassment by looking up whether you've been wrong for thousand of years.