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. 



shallow question: Why a 300 digit number is associated with "any NP-hard problem"?
Euclid's algorithm for computing the GCD of two numbers [is linear time computable](https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm) in the number of digits in each of the two numbers. Meanwhile, it is known by the [time hierarchy theorems](http://en.wikipedia.org/wiki/Time_hierarchy_theorem#Consequences) 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...


