From single to double use expressions, with applications to parametric interval linear systems: On computational complexity of fuzzy and interval computations
Joe Lorkowski · 2011
In many practical problems, we need to estimate the range of a given expression f(x1, ..., xn) when each input xibelongs to a known interval [xi, xi] - or when each input xiis described by a known fuzzy set. It is known that this problem is easy to solve when we have a Single Use Expression, i.e., an expression in which each variable xioccurs only once. In this paper, we show that for similarly defined Double Use Expressions, the corresponding range estimation problem is NP-hard. Similar problems are analyzed for the problem of solving linear systems under interval (and fuzzy) uncertainty.