# Order Of Magnitude Comparisons Of Distance

## Ernest Davis

Courant Institute New York, NY 10012 USA
DAVISEQCS. NYU. EDU

## Abstract

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. This paper exhibits an interesting class of constraint sets in which order of magnitude reasoning is demonstrably fast. Specifically, we present a polynomial-time algorithm that can solve a set of constraints of the form "Points a and b are much closer together than points c and d ."  We prove that this algorithm can be applied if "much closer together" is interpreted either as referring to an infinite difference in scale or as referring to a finite difference in scale, as long as the difference in scale is greater than the number of variables in the constraint set. We also prove that the first-order theory over such constraints is decidable.

## 1. 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, 199).

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²α(n)), ne, s) where n is the number of variables, α( 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