We study some problems in interval arithmetic treated in
Kreinovich et al. [13]. 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 analogous class
NP
. Our results substantiate that most likely it does not any longer capture the difficulty of
NP
in such a real number setting. More precisely, we give upper complexity bounds for the approximation problem for interval functions by locating it in (a real analogue of). This result allows several conclusions:
the problem is not (any more)
NP
-hard under so called weak polynomial time reductions and likely not to be
NP
-hard under (full) polynomial time reductions;
for fixed dimension the problem is polynomial time solvable; this extends the results in
Koshelev et al. [12] and answers a question left open in [13].
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.