Deciding if given number is a permanent of matrix

Question

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?

Answer 1

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.