ALCOMFT-TR-03-34

Klaus Meer
On the complexity of some problems in interval arithmetic
Århus. Work package 4. September 2003.

Abstract: We study some problems in interval arithmetic treated in 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_R. Our results substantiate that most likely it does not any longer capture the difficulty of NP_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 D\sum²_R (a real analogue of \sum²). This result allows several conclusions:
# - the problem is not (any more) NP_R-hard under so called weak polynomial time reductions and likely not to be NP_R-hard under (full) polynomial time reductions;
# - for fixed dimension the problem is polynomial time solvable; this extends the results in Koshelev et al. and answers a question left open by Kreinovich.
# 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.

Postscript file: ALCOMFT-TR-03-34.ps.gz (109 kb).