Society for Industrial and Applied Mathematics, 1986, -96 pp.
There is little doubt that the present explosion of interest in the algorithmic aspects of mathematics is due to the development of computers — even though special algorithms and their study can be traced back all the way through the history of mathematics. Mathematics started out in Egypt and Babylon as a clearly algorithmic science. In ancient Greece the foundations of its "descriptive" or "structural" line were established; but even here we find algorithmic problems — just think of the problem of constructibility of various geometric figures by compass and ruler. I find it amazing that this problem was precisely formulated in the framework of axiomatic geometry (reflecting the current state of devices at the disposal of the Greeks when they were carrying out those constructions). It is unnecessary to say how much this problem contributed to the later development of geometry and to the creation of algebra: both the positive and the negative results inspired fundamental notions and theorems (e.g. the golden ratio on the one hand and the solvability of algebraic equations by radicals, in particular by square roots, on the other).
In our day, the development of computers and the theory of algorithms and their complexity have produced a similar situation. In the last centuries, a vast body of "structural" mathematics has evolved. Now that we are interested in the algorithmic aspects of these results, we meet extremely difficult problems. Some of the most elementary results in number theory, geometry, algebra, or calculus become utterly difficult when we ask for algorithms to find those objects whose existence is (at least by now) easily established. Just think of the elementary fact, known to Euclid, that any integer has a unique prime factorization, and contrast it with the apparent intractability of the corresponding algorithmic problem, namely, the problem of finding this decomposition.
How to Round Numbers.
How to Round a Convex Body.
Some Applications in Combinatorics.
There is little doubt that the present explosion of interest in the algorithmic aspects of mathematics is due to the development of computers — even though special algorithms and their study can be traced back all the way through the history of mathematics. Mathematics started out in Egypt and Babylon as a clearly algorithmic science. In ancient Greece the foundations of its "descriptive" or "structural" line were established; but even here we find algorithmic problems — just think of the problem of constructibility of various geometric figures by compass and ruler. I find it amazing that this problem was precisely formulated in the framework of axiomatic geometry (reflecting the current state of devices at the disposal of the Greeks when they were carrying out those constructions). It is unnecessary to say how much this problem contributed to the later development of geometry and to the creation of algebra: both the positive and the negative results inspired fundamental notions and theorems (e.g. the golden ratio on the one hand and the solvability of algebraic equations by radicals, in particular by square roots, on the other).
In our day, the development of computers and the theory of algorithms and their complexity have produced a similar situation. In the last centuries, a vast body of "structural" mathematics has evolved. Now that we are interested in the algorithmic aspects of these results, we meet extremely difficult problems. Some of the most elementary results in number theory, geometry, algebra, or calculus become utterly difficult when we ask for algorithms to find those objects whose existence is (at least by now) easily established. Just think of the elementary fact, known to Euclid, that any integer has a unique prime factorization, and contrast it with the apparent intractability of the corresponding algorithmic problem, namely, the problem of finding this decomposition.
How to Round Numbers.
How to Round a Convex Body.
Some Applications in Combinatorics.