NP-hard classes of linear algebraic systems with uncertainties (Q1362824): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
| Property / author | |||
| Property / author: Vladik Ya. Kreinovich / rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Andreas Frommer / rank | |||
Revision as of 22:12, 10 February 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
