Abstract
We show that if we add at least one non-interval set to the family of all intervals, then some reasonable interval computation problems that were previously computationally feasible become intractable. This result provides one more motivation for using the interval family: because if we increase this family, we lose computability.
Similar content being viewed by others
References
Gaganov, A. A.: Computational Complexity of the Range of the Polynomial in Several Variables, Cybernetics (1985), pp. 418–421.
Garey, M. R. and Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Nogueira, M., Nandigam, A. Why Intervals? Because If We Allow Other Sets, Tractable Problems Become Intractable. Reliable Computing 4, 389–394 (1998). https://doi.org/10.1023/A:1024475901686
Issue Date:
DOI: https://doi.org/10.1023/A:1024475901686