Consider a commutative semiring . is the identity for , and is the identity for . Let , and . It is common that we are interested in computing expressions of the following form.
If for all , and be the probability that event occurs, , we find the probability that the number of event occurs times, where . In probability, this is computing the Poisson distribution.
If , , for all and and and , then we find the number of subsets that have element sum .
If , , and , then this solves the knapsack problem with knapsack size , value and cost .
An actual application inspired this post: An automated test suite that runs subtests, and it is allowed to rerun a subtest if it fails the first time. A subtest passes if first run passes or the rerun passes. The test is successful if all the subtests passes and the number of total reruns is at most . Assume probability of passing is independent for each subtest. One want to estimate the probability of a successful test given the probability a run passes for a specific subtest.
Let and . The naive algorithm runs in time (assuming semiring operation takes time). There is a common transformation that turns this problem that sum over all subsets to a problem that sums over . So it runs in time.
Let and . Define .
We only incur a number of semiring operations once we compute all for .
Let be the Iverson bracket notation, namely
- For , .
The base case can be verified easily, we show part of a inductive step.