Mathematics and Computer Science: Coping with Finiteness

See allHide authors and affiliations

Science  17 Dec 1976:
Vol. 194, Issue 4271, pp. 1235-1242
DOI: 10.1126/science.194.4271.1235


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.

Stay Connected to Science

Editor's Blog