RECORD
Exact interval solutions to the discrete Bellman equation and polynomial complexity of problems in interval idempotent linear algebra
Rings and Algebras · Submitted 5 Jan 2001
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim In the note we consider matrix equations over positive semirings; in this case the computational complexity of the problem is polynomial.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
In this note we construct a solution of a matrix interval linear equation of the form X=AX+B (the discrete stationary Bellman equation) over partially ordered semirings, including the semiring of nonnegative real numbers and all idempotent semirings. We discuss also the computational complexity of problems in interval idempotent linear algebra. In the traditional Interval Analysis problems of this kind are generally NP-hard. In the note we consider matrix equations over positive semirings; in this case the computational complexity of the problem is polynomial. Idempotent and other positive semirings arise naturally in optimization problems. Many of these problems turn out to be linear over appropriate idempotent semirings. In this case, the system of equations X=AX+B appears to be a natural analog of a usual linear system in the traditional linear algebra over fields. B. A. Carre showed that many of the well-known algorithms of discrete optimization are analogous to standard algorithms of the traditional computational linear algebra.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | In this note we construct a solution of a matrix interval linear equation of the form X=AX+B (the discrete stationary Bellman equation) over partially ordered semirings, including the semiring of nonnegative real numbers and all idempotent semirings. | contribution 0.97 | 0.96 | 0.34 | asserted 1.00 |
| s1 | We discuss also the computational complexity of problems in interval idempotent linear algebra. | contribution 0.99 | 0.73 | 0.07 | asserted 0.64 |
| s2 | In the traditional Interval Analysis problems of this kind are generally NP-hard. | background 0.99 | 0.06 | 0.06 | asserted 0.96 |
| s3 | In the note we consider matrix equations over positive semirings; in this case the computational complexity of the problem is polynomial. | result 0.96 | 0.73 | 0.56 | asserted 1.00 |
| s4 | Idempotent and other positive semirings arise naturally in optimization problems. | background 0.99 | 0.10 | 0.04 | asserted 0.98 |
| s5 | Many of these problems turn out to be linear over appropriate idempotent semirings. | background 0.97 | 0.14 | 0.05 | asserted 0.90 |
| s6 | In this case, the system of equations X=AX+B appears to be a natural analog of a usual linear system in the traditional linear algebra over fields. B. A. | background 0.80 | 0.20 | 0.07 | hedged possibility 0.89 |
| s7 | Carre showed that many of the well-known algorithms of discrete optimization are analogous to standard algorithms of the traditional computational linear algebra. | background 1.00 | 0.04 | 0.03 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
In this note we construct a solution of a matrix interval linear equation of the form X=AX+B (the discrete stationary Bellman equation) over partially ordered semirings, including the semiring of nonnegative real numbers and all idempotent semirings. We discuss also the computational complexity of problems in interval idempotent linear algebra. In the traditional Interval Analysis problems of this kind are generally NP-hard. In the note we consider matrix equations over positive semirings; in this case the computational complexity of the problem is polynomial. Idempotent and other positive semirings arise naturally in optimization problems. Many of these problems turn out to be linear over appropriate idempotent semirings. In this case, the system of equations X=AX+B appears to be a natural analog of a usual linear system in the traditional linear algebra over fields. B. A. Carre showed that many of the well-known algorithms of discrete optimization are analogous to standard algorithms of the traditional computational linear algebra.
Human review
How the literature uses it
1 arXiv paper cite this in 5 sentences
Papers citing it · 4 sentences without a confident label
Cites it as support 1 paper
-
It was noticed in [ref] that in the idempotent case solving an interval linear system requires a polynomial number of operations (similarly to the usual Gauss elimination algorithm).
Idempotent and tropical mathematics. Complexity of algorithms and interval analysis · Interval extensions of algorithms · 0.97
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.