Checking Monotonicity Is NP-Hard Even for
Andrzej Pownuk, Luc Longpr�, Владик Крейнович · 2013
One of the main problems of interval computations is to compute the range of a given function over given intervals. In general, this problem is computationally intractable (NP-hard) – that is why we usually compute an enclosure and not the exact range. However, there are cases when it is possible to feasibly compute the exact range; one of these cases is when the function is monotonic with respect to each of its variables. The monotonicity assumption holds when the derivatives at a midpoint are different from 0 and the intervals are sufficiently narrow; because of this, monotonicity-based estimates are often used as a heuristic method. In situations when it is important to have an enclosure, it is desirable to check whether this estimate is justified, i.e., whether the function is indeed monotonic. It is known that monotonicity can be feasibly checked for quadratic functions. In this paper, we show that for cubic functions, checking monotonicity is NP-hard.