Welcome to MathOverflow

Question

2

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.

edited Feb 11 at 7:32

asked Feb 10 at 10:27

joro
4,260●1●10●31

	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 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 at 22:09
	Tobias Fritz, Günter Rote thank you for the comments. Edited the question. – joro Feb 11 at 7:33
	@Tobias your answer will be interesting, especially if you can explain why some semirings are "easy" – joro Feb 11 at 16:20

Semirings where solving linear systems is in P

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.