NP-hard classes of linear algebraic systems with uncertainties (Q1362824): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Vladik Ya. Kreinovich / rank | |||
Property / reviewed by | |||
Property / reviewed by: Andreas Frommer / rank | |||
Property / author | |||
Property / author: Vladik Ya. Kreinovich / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Andreas Frommer / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
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