Tagged Questions

7
votes
1answer
256 views

Exact arithmetic complexity of Ryser's formula for computing permanent

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 ...
17
votes
1answer
619 views

Can we decide whether a permanent has a unique term?

Suppose we are given an n by n matrix, M, with integer entries. Can we decide in P whether there is a permutation $\sigma$ such that for all permutations $\pi\ne\sigma$ we have $\Pi M_{i\sigma(i)}\ne ...