NP-hard classes of linear algebraic systems with uncertainties (Q1362824): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 04:04, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | NP-hard classes of linear algebraic systems with uncertainties |
scientific article |
Statements
NP-hard classes of linear algebraic systems with uncertainties (English)
0 references
18 September 1997
0 references
This paper considers `linear equations' \((m\) equations, \(n\) unknowns), where the matrix entries as well as the right hand side entries may depend on several parameters. One question is to decide whether such a system admits a solution for at least one parameter configuration. The authors show that this -- and similar -- problems are ordinarily NP-hard, even if one restricts the class of `linear equations' to smaller subclasses like interval matrices or positive interval matrices.
0 references
NP-hard classes
0 references
linear algebraic systems
0 references
complexity
0 references
interval systems
0 references
parameter dependence
0 references
interval matrices
0 references