Let $S$ be a commutative semiring and $T\subset S$, how many semiring operations are required to compute the following $$\prod_{a,b\in T} a+b$$?

This problem can be solved for commutative rings in $O(n \log n)$ ring operations using multipoint polynomial evaluation from a related problem. However, the algorithm requires there is an inverse to addition.

Actually I'm mostly interested in a similar problem. We have $M = \{A_1,\ldots,A_k\}$ such that $A_i\subset S$. We want to compute

$$\prod_{A\in M} \prod_{A\neq B\in M} \prod_{a\in A,b\in B} a+b$$

with least number of semiring operations.


Not an answer to your exact question, but may be useful if you happen to have a semiring with cancellation: if you have an algorithm which works in any ring, you can apply that algorithm to the difference ring $S-S$ consisting of subtraction pairs $s - t$. The result will have the form $s - t$ where $s,t \in S$, and the answer will be $d \in S$ s.t. $s = d + t$. Thus, in addition to semiring operations, you'd need to perform a single cancellation step at the end.

| cite | improve this answer | |
  • 1
    $\begingroup$ A difference ring can be defined only for a semiring with the cancellation property with respect to addition (x+z=y+z ⇒ x=y). For example, the (min, +) semiring on ℕ∪{∞} does not have the cancellation property. Therefore, I do not think that this trick works. $\endgroup$ – Tsuyoshi Ito Feb 15 '13 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.