Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Science 17 December 1976:
Vol. 194. no. 4271, pp. 1235 - 1242
DOI: 10.1126/science.194.4271.1235
Prev | Table of Contents | Next

Articles

Mathematics and Computer Science: Coping with Finiteness

Donald E. Knuth 1

1 Professor of computer science at Stanford University, Stanford, California 94305

By presenting these examples, I have tried to illustrate four main points.

1) Finite numbers can be really enormous, and the known universe is very small. Therefore the distinction between finite and infinite is not as relevant as the distinction between realistic and unrealistic.

2) In many cases there are subtle ways to solve very large problems quickly, in spite of the fact that they appear at first to require examination of too many possibilities.

3) There are also cases where we can prove that a fairly natural problem is intrinsically hard, far beyond our conceivable capabilities.

4) It takes a good deal of skill to decide whether a given problem is in the easy or hard class; but even if a problem does turn out to be hard there are useful and interesting ways to change it into one that can be done satisfactorily.


THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
Computers and Research.
W. O. Baker, W. S. Brown, M. V. Mathews, S. P. Morgan, H. O. Pollak, R. C. Prim, and S. Sternberg (1977)
Science 195, 1134-1139
   PDF »


To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)