Examples

Consider the following inferences:

Example 1: I wish to buy a house and rent office space in a suburb of Metropolis. For obvious reasons, I want the house to be close to the school, the house to be close to the office, and the office to be close to the commuter train station. I am told that in Elmville the train station is quite far from the school, but in Newton they are close together.

Infer that I will not be able to satisfy my constraints in Elmville, but may be able to in Newton.

Example 2: The Empire State Building is much closer to the Washington Monument than to Versailles. The Statue of Liberty is much closer both to the Empire State Building and to Carnegie Hall than to the Washington Monument.

Infer that Carnegie Hall is much closer to the Empire State Building than to Versailles.

Example 3: You have to carry out a collection of computational tasks covering a wide range of difficulty. For instance

a.

Add up a column of 100 numbers.

b.

Sort a list of 10,000 elements.

c.

Invert a 100x100 matrix.

d.

Invert a 1000x1000 matrix.

e.

Given the O.D.E. d²x/dt² = cos(e^tx), x(0)= 0, find x(20) to 32-bit accuracy.

f.

Given a online collection of 1,000 photographs in GIF format, use state-of-the-art image recognition software to select all those that show a man on horseback.

g.

Do a Web search until you have collected 100 pictures of men on horseback, using state-of-the-art image recognition software.

h.

Using state-of-the-art theorem proving software, find a proof that the medians of a triangle are concurrent.

i.

Using state-of-the-art theorem proving software, find a proof of Fermat's little theorem.

It is plausible to suppose that, in many of these cases, you can say reliably that one task will take much longer than another, either by a human judgment or using an expert system. For instance, task (a) is much shorter than any of the others. Task (b) is much shorter than any of the others except (a) and possibly (h). Task (c) is certainly much shorter than (d), (f), (g), or (i). However, with certain pairs such as (c) and (h) or (c) and (e) it would be difficult to guess whether one is much shorter than another, or whether they are of comparable difficulty.

You have a number of independent identical computers, of unknown vintage and characteristics, on which you will schedule tasks of these kinds. Note that, under these circumstances, there is no way to predict the absolute time required by any of these tasks within a couple of orders of magnitude. Nonetheless, the comparative lengths presumably still stand.

Given: a particular schedule of tasks on machines, infer what you can about the relative order of completion times. For example, given the following schedule

Machine M1: tasks a,b,h,d.
Machine M2: tasks c,i.

it should be possible to predict that (a) and (b) will complete before (c); that (c) will complete before (d); and that (d) will complete before (i); but it will not be possible to predict the order in which (c) and (h) will complete.

In all three examples, the given information has the form ``The distance between points W and X is much less than the distance between Y and Z''. In examples 1 and 2, the points are geometric. In example 3, the points are the start and completion times of the various tasks, and the constraints on relative lengths can be put in the form ``The distance from start(a) to end(a) is much less than the distance from start(c) to end(c)'', and so on. In example 3, there is also ordering information: the start of each task precedes its end; the end of (a) is equal to the start of (b); and so on. The problem is to make inferences based on this weak kind of constraint.

It should be noted that these examples are meant to be illustrative, rather than serious applications. Example 1 does not extend in any obvious way to a class of natural, large problems. Example 2 is implausible as a state of knowledge; how does the reasoner find himself knowing just the order-of-magnitude relations among distances and no other geometric information? Example 3 is contrived. Nonetheless, these illustrate the kinds of situations where order-of-magnitude relations on distance do arise; where they express a substantial part of the knowledge of the reasoner; and where inferences based purely on the order-of-magnitude comparisons can yield useful conclusions.

The methods presented in this paper involve construing the relation ``Distance D is much shorter than distance E'' as if it were ``Distance D is infinitesimal as compared to distance E.'' As we shall see, under this interpretation, systems of constraints over distances can be solved efficiently. The logical foundations for dealing with infinitesimal quantities lie in the non-standard model of the real line with infinitesimals, developed by Abraham Robinson (1965). (A more readable account is given by Keisler, 1976.) Reasoning with quantities of infinitely different scale is known as ``order of magnitude'' reasoning.

The reader may ask, ``Since infinitesimals have no physical reality, what is the value of developing techniques for reasoning about them?'' In none of the examples, after all, is the smaller quantity truly infinitesimal or the larger one truly infinite. In example 1 and 2, the ratio between successive sizes is somewhere between 10 and 100; in example 3, it is between 100 and a rather large number difficult to estimate; but one can always give some kind of upper bound. It is essentially certain, for instance, that the ratio between the times required for tasks (a) and (i) is less than 10^100,000. Why not use the best real-valued estimate instead?

The first answer is that this is an idealization. Practically all physical reasoning and calculation rest on one idealization or another: the idealization in the situation calculus that time is discrete; the idealization that solid objects are rigid, employed in most mechanics programs; the idealization that such physical properties as density, temperature, and pressure are continuous rather than local averages over atoms, which underlies most uses of partial differential equations; the idealization involved in the use of the Dirac delta function; and so on. Our idealization here that a very short distance is infinitesimally smaller than a long one simplifies reasoning and yields useful results as long as care is taken to stay within an appropriate range of application.

The second answer is that this is a technique of mathematical approximation, which we are using to turn an intractable problem into a tractable one. This would be analogous to linearizing a non-linear equation over a small neighborhood; or to approximating a sum by an integral.

There are circumstances where we can be sure that the approximation gives an answer that is guaranteed exactly correct; namely if the actual ratio implicit in the comparison ``D is much smaller than E'' is larger than the number of points involved in the system of constraints. This will be proven in section 7. There is also a broader, less well-defined, class of problems where the approximation, though not guaranteed correct, is more reliable than some of the other links in the reasoning. For instance, suppose that one were to consider an instance of example 3 involving a couple of hundred tasks, apply order-of-magnitude reasoning, and come up with an answer that can be determined to be wrong. It is possible that the error would be due to the order-of-magnitude reasoning. However, it seems safe to say that, in most cases, the error is more likely to be due to a mistake in estimating the comparative sizes.