Abstract of Paper

On the complexity of some problems in interval arithmetic
by Klaus Meer

Abstract:

We study some problems in interval arithmetic treated by {\it Kreinovich et al.}
First, we consider the best linear approximation of a quadratic interval function.
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_{\mathcal R}.$ Our results substantiate that most likely it does not any
longer capture the difficulty of $NP_{\mathcal 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 $\Sigma2_{\mathcal R}$ (a real analogue
of $\Sigma2).$

This result allows several conclusions:

- the problem is not (any more) $NP_{\mathcal R}$-hard under
  so called weak polynomial time reductions and likely not to be
  $NP_{\mathcal 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 theory
with issues from semi-infinite optimization theory.