Complexity refinement of some problems in interval arithmetic using real number complexity theory

Klaus Meer

We study some problems in interval arithmetic treated by Kreinovich et al. First, we consider the best linear approximation of a quadratic interval function (a semi-infinite optimization problem). Whereas this problem (as decision problem) is known to be $NP$-hard in the Turing model, we analyze its complexity in the real number model and the analoguous class $NP_{\mathbb{R}}.$ Our results substantiate that most likely it does not any longer capture the difficulty of $NP_{\mathbb{R}}$ in such a real number setting. More precisely, we give upper complexity bounds for the approximation problem for interval functions by locating it in $\Sigma^2_{\mathbb{R}}$ (a real analogue of $\Sigma^2).$

This result allows several conclusions:

- the problem is not (any more) $NP_{\mathbb{R}}$-hard under so called weak polynomial time reductions and likely not to be $NP_{\mathbb{R}}$-hard under (full) polynomial time reductions;

- for fixed dimension the problem is polynomial time solvable; this extends results by Koshelev et al. and answers a question left open in by Kreinovich et al.

We also study several versions of interval linear systems and show similar results as for the approximation problem. Our methods combine structural complexity thory with issues from semi-infinite optimization theory.