Timeline for Semirings where solving linear systems is in P
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 11, 2013 at 16:20 | comment | added | joro | @Tobias your answer will be interesting, especially if you can explain why some semirings are "easy" | |
| Feb 11, 2013 at 7:33 | comment | added | joro | Tobias Fritz, Günter Rote thank you for the comments. Edited the question. | |
| Feb 11, 2013 at 7:32 | history | edited | joro | CC BY-SA 3.0 |
clarifications
|
| Feb 10, 2013 at 22:09 | comment | added | Günter Rote | 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? | |
| Feb 10, 2013 at 21:51 | comment | added | Tobias Fritz | 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). | |
| Feb 10, 2013 at 10:27 | history | asked | joro | CC BY-SA 3.0 |