Examples

**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= cos(^{2}x/dt^{2}e^{t}x),x(0)= 0, findx(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.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.

Machine M2: tasks c,i.

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.