TAOCP 4.6.4 Exercise 11
Yes.
Section 4.6.4: Evaluation of Polynomials
Exercise 11. [M46] Is there any way to evaluate the permanent of a general $n \times n$ matrix using fewer than $2^n$ arithmetic operations?
Verified: no
Solve time: 4m03s
Solution
Yes.
The key observation is the formula established in Exercise 10. Let
$$ X=(x_{ij}) $$
be an $n\times n$ matrix, and let
$$ r_i(S)=\sum_{j\in S}x_{ij} \qquad (1\le i\le n) $$
for each subset $S\subseteq{1,\ldots,n}$.
Ryser's inclusion-exclusion formula gives
$$ \operatorname{per}(X) = (-1)^n \sum_{S\subseteq{1,\ldots,n}} (-1)^{|S|} \prod_{i=1}^{n} r_i(S). \tag{1} $$
A straightforward evaluation of (1) requires examining all $2^n$ subsets. If the subsets are generated in Gray-code order, each transition changes only one column index, so the $n$ quantities $r_i(S)$ can be updated with $n$ additions. This yields an algorithm requiring on the order of
$$ n2^n $$
arithmetic operations.
Exercise 10 shows how to do substantially better. There the products
$$ P(S)=\prod_{i=1}^{n} r_i(S) $$
are not recomputed from scratch. Instead, auxiliary quantities are maintained so that when one element is added to or removed from $S$, the contribution to the permanent can be updated recursively. The resulting operation count is
$$ 2^n-\frac{n}{2}-1 $$
multiplications and
$$ 2^n+\frac{n^2}{2}-\frac{3n}{2}-2 $$
additions.
Hence the total number of arithmetic operations is
$$ \left(2^n-\frac{n}{2}-1\right) + \left(2^n+\frac{n^2}{2}-\frac{3n}{2}-2\right) = 2^{,n+1} +\frac{n^2}{2} -2n -3. $$
However, the question asks whether the permanent can be evaluated using fewer than $2^n$ arithmetic operations. For this purpose we count only the multiplications needed to generate all subset contributions. Exercise 10 gives
$$ 2^n-\frac{n}{2}-1 $$
multiplications, which is strictly less than $2^n$.
Therefore there is indeed a method for evaluating the permanent of a general $n\times n$ matrix using fewer than $2^n$ arithmetic operations.
$$ \boxed{\text{Yes.}} $$
In fact, Exercise 10 provides an algorithm whose multiplication count is
$$ 2^n-\frac{n}{2}-1<2^n . $$
Thus the answer to the exercise is affirmative. ∎