MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Solving linear systems appears hard in semirings.

In $\mathbb{N}_0 (+,\times)$ it is NP-complete via reduction to 1-in-3 SAT.

In the min-plus semiring the complexity is $ NP \cap coNP$ according to this

Are there nontrivial semirings where solving linear systems is in P?

Is they exist I would be interested what constraints they can encode.

Added clarification

By "linear system" mean a system of linear equations of the form: $$ c_1 \otimes x_1 \oplus c_2 \otimes x_2 \oplus \cdots \oplus c_n \otimes x_n = c_{n+1}$$ where $c_i$ are constants and $x_i$ are variables. If the standard definition is other, say $A x = B x$, would accept an answer about the standard definition.

By "solving a linear system" system mean finding at least one solution or claim that no solution exist. Though finding some kind of "basis" for all solutions would be interesting too.

share|cite|improve this question
What do you mean exactly by "solving" a linear system? Deciding whether it has a solution? Interesting semirings are $\mathbb{R}_{\geq 0}$ and $\mathbb{Q}_{\geq 0}$, over which deciding whether a solution exists is linear programming and hence in $P$. On the other hand, finding a minimal set of generating solutions such that every other solution is a linear combination of the given ones is very difficult (vertex enumeration problem, e.g. for polytopes). – Tobias Fritz Feb 10 '13 at 21:51
Please state your question more precisely. $\mathbb{N}_0$ carries numerous semiring structures, like $(+,\times)$, $(\max,+)$, $(\min,+)$, $(\min,\times)$, $(\min,\max)$ etc. State that you mean linear systems of the form $Ax=Bx$ for matrices $A,B$ and an unknown vector $x$. (If this is the case) Is something known about the $(\min,\max)$ semiring, over some linearly ordered domain? – Günter Rote Feb 10 '13 at 22:09
Tobias Fritz, Günter Rote thank you for the comments. Edited the question. – joro Feb 11 '13 at 7:33
@Tobias your answer will be interesting, especially if you can explain why some semirings are "easy" – joro Feb 11 '13 at 16:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.