3
votes
0answers
120 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 ...