Every Function Computable by an Arithmetic Single Use Expression is a Ratio of Two Multi-Linear Functions: A Theorem

摘要

One of the main problems of interval computation is computing the range of a given function on a given box. In general, computing the exact range is a computationally difficult (NP-hard) problem, but there are important cases when a feasible algorithm for computing such a function is possible. One of such cases is the case of singe-use expressions (SUE), when each variable occurs only once. Because of this, practitioners often try to come up with a SUE expression for computing a given function. It is therefore important to know when such a SUE expression is possible. In this paper, we consider the case of functions that can be computed by using only arithmetic operations (addition, subtraction, multiplication, and division). We show that when there exists a SUE expression for computing such a function, then this function is equal to a ratio of two multi-linear functions (although there are ratios of multi-linear functions for which no SUE expression is possible). Thus, if a function is not equal to such a ratio, then we should not waste our efforts on finding a SUE expression for computing this function.