Enclosing solutions of linear interval equations is NP-hard
type: Item
instance of: scholarly article
title: Enclosing solutions of linear interval equations is NP-hard
zbMATH Open document ID: 0809.65019
DOI: 10.1007/BF02307386
published in: Computing
publication date: 1994-12-20T00:00:00Z
review text: Assume that not any problem solvable by a nondeterministic polynomial- time algorithm can also be solved by a polynomial-time algorithm. Then it is shown that there does not exist a polynomial-time algorithm which for each \(n\times n\) interval matrix \(A^ I\) and each interval vector \(b^ I\) with \(n\) components would --- yield an enclosure of the solution set \(X(A^ I,b^ I):= \{x\mid Ax= b\) for some \(A\in A^ I\), \(b\in b^ I\}\) provided \(X(A^ I,b^ I)\) is bounded, --- issue an error message if \(X(A^ I,b^ I)\) is unbounded.
reviewed by: Günter Mayer
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65G30
Mathematics Subject Classification ID: 15A06
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 704633
zbMATH Keywords: linear interval equations
zbMATH Keywords: enclosure method
zbMATH Keywords: NP-hardness
zbMATH Keywords: solution set of interval systems
zbMATH Keywords: polynomial-time algorithm
author: Jiří Rohn
MaRDI profile type: Publication
cites work: Q3345690
cites work: Q4198056
cites work: Interval Methods for Systems of Equations
cites work: Checking robust nonsingularity is NP-hard
cites work: Abbruch beim Intervall-Gauß-Algorithmus
cites work: Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
cites work: Q3818127
full work available at URL: https://doi.org/10.1007/bf02307386
OpenAlex ID: W152607821
description: scientific article; zbMATH DE number 704633