# Deciding if given number is a permanent of matrix

The permanent of an $$n$$-by- $$n$$ matrix $$A=\left(a_{i j}\right)$$ is defined as $$\operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)}$$ The sum here extends over all elements $$\sigma$$ of the symmetric group $$S_{n}$$ i.e. over all permutations of the numbers $$1,2, \ldots, n$$. $$\operatorname{perm}\left(\begin{array}{ll} a & b \\ c & d \end{array}\right)=a d+b c$$

Given number $$N$$ and matrix $$A$$, is it possible to check for $$N$$ being permanent of the $$A$$ in polynomial time? Or are fast verification algorithms not guaranteed for #P-complete problems?

• Of course there are many such verification problems one can ask; is there a reason to suspect that this might be possible specifically for the permanent problem? Commented Aug 20, 2022 at 16:03
• A #P-complete problem such as Permanent cannot have a polynomial-time verification algorithm unless all of the counting hierarchy CH collapses down to NP, or even to $\mathrm{UP\cap coUP}$. Commented Aug 20, 2022 at 16:12
• In fact, IIRC, Permanent is #P-complete under parsimonius reductions, which implies that the permanent verification problem is $C_=P$-complete. Since $\mathrm{PP\subseteq UP^{C_=P}\subseteq C_=P^{C_=P}}$, this shows that if the problem is in polynomial time, then CH collapses to P. Commented Aug 21, 2022 at 7:12
• @EmilJeřábek Thanks! Submit it as a question, I'll approve it. Commented Aug 21, 2022 at 9:24
• Now that I have had a coffee, Permanent is of course not #P-complete under parsimonious reductions unless $P=\oplus P$, as it is polynomial-time computable modulo 2. But Valiant’s reduction is still good enough to make the rest of the argument work. I’ll post an answer later. Commented Aug 22, 2022 at 8:17

## 1 Answer

First, there is a subtlety: the permanent of nonnegative integer matrices is computable in #P, and it is #P-complete even for $$\{0,1\}$$-matrices. However, the permanent of general integer matrices is only in GapP (i.e., it is the difference of two #P-functions); I believe it is GapP-complete, though I cannot find a good reference at the moment.

The graph of the permanent (or permanent verification, as the question puts it) $$\mathrm{PermGraph}=\{(A,N):A\in\mathbb Z^{n\times n},N=\operatorname{perm}(A)\}$$ belongs to the class $$\mathbf{C_=P}$$, which consists of decision problems $$L$$ such that $$\tag1x\in L\iff f(x)=h(x)$$ for some $$f\in\mathbf{\#P}$$ and $$h\in\mathbf{FP}$$, or equivalently, such that $$x\in L\iff g(x)=0$$ for some $$g\in\mathbf{GapP}$$.

In fact, PermGraph is $$\mathbf{C_=P}$$-complete. This follows easily from Valiant’s reduction: #3SAT is #P-complete under parsimonious reductions, and given a 3CNF $$\phi$$ with $$s(\phi)$$ satisfying assignments, Valiant constructs a $$\{-1,0,1,2,3\}$$-matrix $$A_\phi$$ such that $$\operatorname{perm}(A_\phi)=4^{t(\phi)}s(\phi)$$ for a certain polynomial-time polynomially bounded function $$t$$. Thus, for $$L\in\mathbf{C_=P}$$ expressed as (1), there is a polytime function $$x\mapsto\phi_x$$ such that $$f(x)=s(\phi_x)$$, and we have $$x\in L\iff(A_{\phi_x},4^{t(\phi_x)}h(x))\in\mathrm{PermGraph}.$$

Now, what does this tell us about the complexity of PermGraph? The classes #P, GapP, and their decision version PP have more-or-less the same complexity (they are polynomial-time Turing-reducible to each other). The class $$\mathbf{C_=P}$$ seems to be weaker than that, nevertheless it is “half-way through” towards #P: first, observe that $$\mathbf{C_=P}$$ includes the class UP of NP-problems that have at most one witness (and this relativizes: $$\mathbf{UP}^X\subseteq\mathbf{C_=P}^X$$ for any oracle $$X$$); then we have $$\mathbf{PP\subseteq UP^{C_=P}\subseteq C_=P^{C_=P}}.$$ Indeed, if $$L\in\mathbf{PP}$$, there are $$f\in\mathbf{\#P}$$ and $$h\in\mathbf{FP}$$ such that $$\tag2x\in L\iff f(x)\ge h(x)\iff\exists y\:(f(x)=y\land y\ge h(x)),$$ where $$f(x)=y\land y\ge h(x)$$ is a $$\mathbf{C_=P}$$ predicate, and the witness $$y$$ is unique if it exists.

In particular, if $$\mathrm{PermGraph}\in\mathbf P$$, then $$\mathbf{C_=P=P}$$, thus $$\mathbf{PP=P}$$, thus the whole counting hierarchy CH collapses to P (and $$\mathbf{FCH=\#P=FP}$$).

More generally, let $$F$$ be any #P-hard function, and $$G_F$$ its graph. Then an argument similar to (2) shows that $$\mathbf{PP\subseteq UP}^{G_F},$$ therefore (using $$\mathbf{PP^{UP}=PP}$$) $$G_F\in\mathbf P\implies\mathbf{CH=UP\cap coUP}.$$ I’m not sure whether one can bring this down to $$\mathbf{CH=P}$$ in this case.