1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – LSpice
    Commented Aug 20, 2022 at 16:03
  • 3
    $\begingroup$ 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}$. $\endgroup$ Commented Aug 20, 2022 at 16:12
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Aug 21, 2022 at 7:12
  • $\begingroup$ @EmilJeřábek Thanks! Submit it as a question, I'll approve it. $\endgroup$ Commented Aug 21, 2022 at 9:24
  • $\begingroup$ 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. $\endgroup$ Commented Aug 22, 2022 at 8:17

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.