If an Exact Interval Computation Problem is NP-Hard, Then the Approximate Problem is Also NP-Hard: A Meta-Result

摘要

In interval computations, usually, once we prove that a problem of computing the exact range is NP-hard, then it later turns out that the problem of computing this range with a given accuracy is also NP-hard. In this paper, we provide a general explanation for this phenomenon.