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?



Deciding if given number is a permanent of matrix
First, there is a subtlety: the permanent of *nonnegative* integer matrices is computable in [**#P**](https://complexityzoo.net/Complexity_Zoo:Symbols#sharpp), and it is **#P**-complete even for $\{0,1\}$-matrices. However, the permanent of general integer matrices is only in [**GapP**](https://complexityzoo.net/Complexity_Zoo:G#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}$](https://complexityzoo.net/Complexity_Zoo:C#cequalsp), 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**](https://complexityzoo.net/Complexity_Zoo:P#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**](https://complexityzoo.net/Complexity_Zoo:U#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**](https://complexityzoo.net/Complexity_Zoo:C#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.


