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?
 A: 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.
