7
$\begingroup$

What is the exact number of multiplication operations and addition operations needed to calculate the permanent in Ryser's formula (both original and the Gray coded version)?

I am looking reference for an exact count. It seems Cramer rule always is inferior or just par with the Gray coded version. Also Scott Aaronson has a calculation for $4 \times 4$ determinant where he uses Gaussian elimination. He mentions estimating the precise gap between permanent and determinant calculation for $4 \times 4$ is already a notorious open problem.

I am also looking for counts for other calculations/formulas of Permanent.

$\endgroup$
  • 2
    $\begingroup$ It would be useful to add a link to the referred formula (or even mention it inline) $\endgroup$ – Suresh Venkat Nov 8 '11 at 17:42
  • $\begingroup$ A good upperbound seems to be stated in the Wikipedia article so I am confused about the motivation for this question. $\endgroup$ – Kaveh Nov 8 '11 at 22:11
  • $\begingroup$ It's possible the key word here is "exact" i.e without O() ? $\endgroup$ – Suresh Venkat Nov 8 '11 at 23:56
  • 1
    $\begingroup$ @SureshVenkat Yes. Precisely. I am looking reference for an exact count. It seems Cramer rule always is inferior or just par with the Gray coded version. Also Scott Aaronson has a calculation for 4x4 determinant where he uses Gaussian elimination. scottaaronson.com/talks/wildidea.ppt He mentions estimating the precise gap between permanent and determinant calculation for 4x4 is already a notorious open problem. $\endgroup$ – v s Nov 9 '11 at 0:33
  • 2
    $\begingroup$ @vs: thanks for the explanation. :) By the way, it might be better to include what you wrote in the comment about inside the post so other would know why you are interested in the problem without a need to read comments. $\endgroup$ – Kaveh Nov 9 '11 at 0:49
7
$\begingroup$

Ryser: $n(n-2)2^{n-1} + n$ additions and $(n-1)(2^{n}-1)$ multiplications.

Ryser+Gray code: $n(2^{n}-2)$ additions and $(n-1)(2^{n}-1)$ multiplications.

Number of multiplications: For each nonempty subset of $[n]$, $n-1$ multiplications are used to multiply $n$ sums together.

Number of additions for Ryser: for each nonempty $S \subseteq [n]$, and for each $i \in [n]$ you compute $\sum_{j \in S} a_{ij}$ which uses $|S|-1$ additions. $\sum_{\emptyset \neq S \subseteq [n]}(|S|-1) = \sum_{k=1}^{n} (k-1) \binom{n}{k} = \sum_{k=1}^{n} k \binom{n}{k} - \sum_{k=1}^{n} \binom{n}{k} = n2^{n-1} - (2^{n}-1)$.

Additions for Ryser+Gray: The Gray code version does not give you a smaller formula, but only a smaller circuit (which is still good, I just thought it was worth pointing out). Its savings require the re-use of previously computed quantities. For each $i \in [n]$, it does a Gray code over the nonempty sets $S \subseteq [n]$. Since there are $2^{n}-1$ such sets, and each transition of the Gray code involves a single addition/substraction, that gives the $2^{n}-2$.

$\endgroup$
  • $\begingroup$ Are you sure about Ryser + Gray count? It seems to give $3 \times 6 + 2 \times 7=32$ total for $n=3$. However, brute force would give $2(3!)$ multiplies and $3!-1$ additions which will be $17$. For $n=4$, your count gives is $4 \times 14 + 3 \times 15=101$ while brute force would give $3(4!)+4!-1=95$. The gap reduces but still was just wondering! $\endgroup$ – v s Nov 9 '11 at 13:01
  • 1
    $\begingroup$ You can check my reasoning. I'm pretty sure I did it right, but of course it's possible I made a mistake. I would not find it too surprising if either of these algorithms were less efficient than brute force for very small input sizes. After all, as a simpler example, $n! < 2^{n}$ when $n < 4$. $\endgroup$ – Joshua Grochow Nov 9 '11 at 19:05

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.