3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – Tobias Fritz
    Commented Feb 10, 2013 at 21:51
  • $\begingroup$ 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? $\endgroup$
    – Günter Rote
    Commented Feb 10, 2013 at 22:09
  • $\begingroup$ Tobias Fritz, Günter Rote thank you for the comments. Edited the question. $\endgroup$
    – joro
    Commented Feb 11, 2013 at 7:33
  • $\begingroup$ @Tobias your answer will be interesting, especially if you can explain why some semirings are "easy" $\endgroup$
    – joro
    Commented Feb 11, 2013 at 16:20

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .