2
votes
0answers
109 views

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