# Complexity of permanent verification

Consider the problem of permanent verification:

$$\bullet \$$ Given a $$n\times n$$ matrix $$A$$ with entries in $$\{0,1\}$$, and given $$k\ge 0$$, does $$Per(A)=k$$?

Question: Is it known to be NP-hard? Should one expect this problem to be in C$$_{=}$$P-complete? (or maybe this is also already known?)

P.S. I might be naive and this is super easy, but excessive googling did not show anything.

• Hmm. It’s $\mathrm{C_=P}$-complete for $\{-1,0,1\}$-matrices (and for general integer matrices, of course). Commented Jun 30, 2023 at 5:35
• I think it is indeed NP-hard. (Hopefully I am not writing stupid things...) First, deciding whether a 3-CNF formula has $k$ satisfying assignments is NP-hard since this encompasses the standard 3-SAT. Then Valiant's proof of #P-completeness of the permanent turns a formula $φ$ into a $0,1$-matrix $A_φ$ such that $per(A_φ)$ is a (known) function $f$ of the number of satisfying assignments of $φ$. Valiant's reduction can therefore be seen as a reduction from $(φ, k)$ to $(A_φ, f(k))$, proving the NP-hardness of your problem. Commented Jun 30, 2023 at 12:58
• @Bruno No, that’s the problem. Valiant’s proof works so that $\mathrm{Per}(A_\phi)$ is only congruent to a known function of the number of satisfying assignments modulo a large known number $Q$. You do not know what multiple of $Q$ you added; there are exponentially many possibilities, and computing it is likely #P-hard on its own. Thus, this does not give you a polynomial-time computable $f$. Commented Jun 30, 2023 at 13:49
• @EmilJeřábek I suspected this was too easy. The problem is going from say $\{-1,0,1\}$-matrices to $\{0,1\}$-matrices, right? or do I miss something else? Commented Jun 30, 2023 at 20:38
• @Bruno Yes, as I already mentioned, the reduction up to $\{-1,0,1\}$-matrices does give a well-defined function of the number of satisfying assignments, and shows that the permanent verification problem for $\{-1,0,1\}$-matrices is $\mathrm{C_=P}$-complete. Commented Jul 1, 2023 at 6:26

At the very least, the problem is "hard for the polynomial hierarchy" in the following sense. Let $$PermVerify$$ be the problem specified. Then $$PH \subseteq P^{\#P} \subseteq NP^{PermVerify}$$ The first containment is Toda's theorem. The second follows because for every query to a $$\#P$$ oracle, we can transform it to a 0,1 permanent instance, guess the value of that permanent, then call $$PermVerify$$ to check the guess is correct.
Therefore if $$PermVerify$$ is in $$PH$$, it is in $$\Sigma_k P$$ for some fixed $$k$$, and so $$PH$$ collapses to $$\Sigma_{k+1} P$$. In other words, your problem is not in $$PH$$, unless $$PH$$ collapses to some finite level (considered unlikely). Thus it's probably not in P, BPP, NP, coNP, etc.
Intuitively $$PermVerify$$ should also be hard for classes like $$C_{=}P$$ but as the comments indicate, this doesn't appear to follow directly from the standard references.
• And this argument appears to work more generally for any problem of the form $CHECK(f)$: "given $x$ and $k$, check whether $f(x)=k$" where $f$ is #P-complete.