© 1999 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

Courant Institute

New York University

New York, NY 10012

Email: davise@cs.nyu.edu

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.

- Introduction
- Examples
- Order-of-magnitude spaces
- Cluster Trees
- Constraints
- Extensions and Consequences
- Finite order of magnitude comparison
- The first-order theory
- Conclusions
- Acknowledgements
- Appendix A. Proofs
- References
- About this document ...