Abstract
Our goal is to measure the likelihood of the satisfaction of numerical
constraints in the absence of prior information. We study expressive
constraints, involving arithmetic and complex numerical functions, and
even quantification over numbers. Such problems arise in processing
incomplete data, or analyzing conditions in programs without a priori
bounds on variables. We show that for constraints on n variables,
the proper way to define such a measure is as the limit of the part of
the n-dimensional ball that consists of points satisfying the
constraints, when the radius increases. We prove that the existence of
such a limit is closely related to the notion of o-minimality from
model theory. Thus, for constraints definable with the usual
arithmetic and exponentiation, the likelihood is well defined, but
adding trigonometric functions is problematic. We look at computing
and approximating such likelihoods for order and linear
constraints, and prove an impossibility result for approximating with
multiplicative error. However, as the
likelihood is a number between 0 and 1, an approximation scheme with
additive error is acceptable, and we give it for arbitrary
linear constraints.
Keywords
- Knowledge Representation and Reasoning: Computational Complexity of Reasoning
- Knowledge Representation and Reasoning: Geometric, Spatial, and Temporal Reasoning
- Constraints and SAT: Constraints: Applications
- Constraints and SAT: Constraints: Evaluation and Analysis
