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