# Semirings where solving linear systems is in P

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.

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.
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