shallow question: Why a 300 digit number is associated with "any NP-hard problem"?

Question

I was reading this article (http://www.ams.org/notices/200203/fea-knuth.pdf) the other day and noticed Donald Knuth said something nontrivial: Theoretically we can compute a very large number of magnititude $10^{300}$ (or possibly even larger) and use it via taking greatest common divisor to solve any NP hard problem. He used this example to suggest the patent system is essentially absurd.

Here is the copy of the original paragraph:

"There’s an interesting issue, though. Could you possibly have a patent on a positive integer? It is not inconceivable that if we took a million of the greatest supercomputers today and set them going, they could compute a certain 300-digit constant that would solve any NP-hard problem by taking the GCD of this constant with an input number, or by some other funny combination. This integer would require massive amounts of computation time to find, and if you knew that integer, then you could do all kinds of useful things. Now, is that integer really discovered by man? Or is it something that is God given? When we start thinking of complexity issues, we have to change our viewpoint as to what is in nature and what is invented."

My shallow question(must have already been asked by someone) is: Why finding such a large integer would suffice to solve any $NP$-hard problem? I asked a friend majoring in algorithm design in computer science, and he could not tell me the answer as well. While he explained to me that a $NP$ hard problem can be reduced to finding the GCD, neither he nor I can understand why finding one number is suffice for all applications. I am not sure if this is more appropriate for mathoverflow or stackoverflow.

Answer 1

Euclid's algorithm for computing the GCD of two numbers is linear time computable in the number of digits in each of the two numbers. Meanwhile, it is known by the time hierarchy theorems that there are problems solvable in quadratic time, but not in linear time.

Thus, we cannot solve truly complex problems (or even moderately difficult problems) by computing the GCD with a fixed number.

In particular, there can be no fixed number, such that computing a GCD of that number with an input computes an NP complete problem, unless P=NP.

Meanwhile, of course, if P=NP, then any polynomial time problem, including any linear time problem such as the GCD problem, is NP-complete. Perhaps the point that Knuth may have had in mind is that it is not inconceivable that P=NP, and in this case there could be particular programs, perhaps not very large, that encode an extremely useful quantity of knowledge, solving NP-complete problems by attractive bounds.

I would find it more likely, however, that he didn't really mean that the GCD calculation would solve all instances of an NP-complete problem, but rather only that it would solve an enormously large number of practical instances of such NP-complete problems. Such a number, summing up concisely an enormous amount of important information, would be extremely useful to know---and would seem to be worth a patent---even if the asymptotic usefulness of the number decayed as the input became comparatively large.

But would 300 digits be sufficient for truly impressive effect? I would compare the situation to having a truly enlightening piece of text, coded into 300 digits after compression. With a compression ratio of .9, this would correspond to an essay of 3000 digits, about a page of text. Could we have such a life-changing or game-changing essay? Probably...

Answer 2

My initial idea was, having looked at this now, was to vote to close this as not a real question, since to me it seems clearly based on a misunderstanding. But then decided, possibly unwisely, to elaborate on this in more detail as it is getting long and there is also an other issue.

First, let us recall that this is a transcript from some Q&A session at some public lecture.

The question was

Question: What is your thinking about software patents? There is a big discussion going on in Europe right now about whether software should be patentable.

Now, Knuth's reply in full (but emphasis mine).

Knuth: I’m against patents on things that any student should be expected to discover. There have been an awful lot of software patents in the U.S. for ideas that are completely trivial, and that bothers me a lot. There is an organization that has worked for many years to make patents on all the remaining trivial ideas and then make these available to everyone. The way patenting had been going was threatening to make the software industry stand still. Algorithms are inherently mathematical things that should be as unpatentable as the value of π. But for something nontrivial, something like the interior point method for linear programming, there’s more justification for somebody getting a right to license the method for a short time, instead of keeping it a trade secret. That’s the whole idea of patents; the word patent means “to make public”. I was trained in the culture of mathematics, so I’m not used to charging people a penny every time they use a theorem I proved. But I charge somebody for the time I spend telling them which theorem to apply. It’s okay to charge for services and customization and improvement, but don’t make the algorithms themselves proprietary. There’s an interesting issue, though. Could you possibly have a patent on a positive integer? It is not inconceivable that if we took a million of the greatest supercomputers today and set them going, they could compute a certain 300-digit constant that would solve any NP-hard problem by taking the GCD of this constant with an input number, or by some other funny combination. This integer would require massive amounts of computation time to find, and if you knew that integer, then you could do all kinds of useful things. Now, is that integer really discovered by man? Or is it something that is God given? When we start thinking of complexity issues, we have to change our viewpoint as to what is in nature and what is invented.

So, first it seems clear to me that the sole idea here is to create a somewhat plausible (in the context of a public lecture) scenario where one could make an argument for a patent on a number, or for licensing its use. In the sense that this number could be consider as closer in spirit to some sophisticated numerical-solver than a natural constant (cf the contrasting of interior point method and Pi beforehand).

To further support this idea note that he did not say one computes the GCD, contrary to the impression given in the question, he says (again my emphasis):

by taking the GCD of this constant with an input number, or by some other funny combination.

Clearly there is nothing specific referred to, and all this is just there to convince the audience that one could perhaps theoretically envision a situation where there could be an integer such that

This integer would require massive amounts of computation time to find, and if you knew that integer, then you could do all kinds of useful things.

He could instead have proclaimed that it is not inconceivable one can with lot of effort find some 1000 binary-digit integer that is particularly well-suited for creating keys for some crypotography-protocol or whatever.

Finally, to just say he suggests the patent system is essentially absurd seems like an overstatement to me. His position on this seems quite a bit more nuanced.

It’s okay to charge for services and customization and improvement, but don’t make the algorithms themselves proprietary.

In that sense, I would even say that for this hyopthetical number he would not find it completely absurd to have some licensing scheme for the number itself (yet not for the underlying and surrounding ideas to find it).

Answer 3

No matter how you formalize the question, if we believe that this world is not a computer simulation with a program of decent length with all randomness introduced by some simple standard pseudorandom generator but a truly random chain of events, then it looks like a rare moment of true unforgivable ignorance of Donald Knuth. He had no excuse for not knowing http://en.wikipedia.org/wiki/Kolmogorov_complexity. It is actually much easier for me to believe that gods had a direct communication with him and showed him a part of the program somehow than to believe that he didn't know what he was talking about to the extent described. Well, perhaps this was the case and we are just funny configurations in some game with simple rules (it was Knuth who designed "life", wasn't it?) but I prefer to act under the alternative assumptions, at least for the next few years :).