Introduction

Order of magnitude reasoning -- reasoning by rough comparisons of the sizes of quantities -- is often called ``back of the envelope calculation", with the implication that the calculations are quick though approximate. Previous AI work on order of magnitude reasoning, however, has focussed on its expressive power and inferential structure, not on its computational leverage (Raiman, 1990; Mavrovouniotis and Stephanopoulos, 1990; Davis, 1990; Weld, 1990).

In this paper we exhibit an interesting case where solving a set of order of magnitude comparisons is demonstrably much faster than solving the analogous set of simple order comparisons. Specifically, given a set of constraints of the form ``Points a and b are much closer together than points c and d,'' the consistency of such a set can be determined in low-order polynomial time. By contrast, it is easily shown that solving a set of constraints of the form ``The distance from a to b is less than or equal to the distance from c to d'' in one dimension is NP-complete, and in higher dimensions is as hard as solving an arbitrary set of algebraic constraints over the reals.

In particular, the paper presents the following results:

1.

The algorithm ``solve_constraints(S)'' solves a system of constraints of the form ``Points a and b are infinitely closer than points c and d'' in polynomial time (Section 5).

2.

An improved version of the algorithm runs in time O(max(n²a(n)),ne,s) where n is the number of variables, a(n) is the inverse Ackermann's function, e is the number of edges mentioned in the constraint set, and s is the size of the constraint set. (Section 6.1).

3.

An extended version of the algorithm allows the inclusion of non-strict constraints of the form ``Points a and b are not infinitely further apart than points c and d.'' The running time for this modified algorithm is slower than that of solve_constraints, but still polynomial time. (Section 6.2)

4.

A different extension of the algorithm allows the combination of order of magnitude constraints on distances with order comparisons on the points of the form ``Point a precedes point b.'' (Section 6.3)

5.

The same algorithm can be applied to constraints of the form ``The distance from a to b is less than 1/B times the distance from c to d,'' where B is a given finite value, as long as B is greater than the number of variables in the constraint set. (Section 7)

6.

The first-order theory over such constraints is decidable. (Section 8)

As preliminary steps, we begin with a small example and an informal discussion (section 2). We then give a formal account of order-of-magnitude spaces (section 3) and present a data structure called a cluster tree, which expresses order-of-magnitude distance comparisons (section 4). We conclude the paper with a discussion of the significance of these results (section 9).