<p>At the very least, the problem is &quot;hard for the polynomial hierarchy&quot; in the following sense.
Let <span class="math-container">$PermVerify$</span> be the problem specified. Then
<span class="math-container">$$PH \subseteq P^{\#P} \subseteq NP^{PermVerify}$$</span>
The first containment is Toda's theorem. The second follows because for every query to a <span class="math-container">$\#P$</span> oracle, we can transform it to a 0,1 permanent instance, guess the value of that permanent, then call <span class="math-container">$PermVerify$</span> to check the guess is correct.</p>
<p>Therefore if <span class="math-container">$PermVerify$</span> is in <span class="math-container">$PH$</span>, it is in <span class="math-container">$\Sigma_k P$</span> for some fixed <span class="math-container">$k$</span>, and so <span class="math-container">$PH$</span> collapses to <span class="math-container">$\Sigma_{k+1} P$</span>. In other words, your problem is not in <span class="math-container">$PH$</span>, unless <span class="math-container">$PH$</span> collapses to some finite level (considered unlikely). Thus it's probably not in P, BPP, NP, coNP, etc.</p>
<p>Intuitively <span class="math-container">$PermVerify$</span> should also be hard for classes like <span class="math-container">$C_{=}P$</span> but as the comments indicate, this doesn't appear to follow directly from the standard references.</p>

CC BY-SA 4.0
2023-07-03T21:03:44.623Z
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.
holf
CC BY-SA 4.0
2023-07-05T01:31:19.230Z
Thanks, Ryan!  This is very helpful.
Igor Pak
CC BY-SA 4.0
2023-07-03T15:46:50.023Z
2023-07-03T15:46:50.023Z
Ryan Williams
<p>Consider the problem of <em>permanent verification</em>:</p>
<p><span class="math-container">$\bullet \ $</span> Given a <span class="math-container">$n\times n$</span> matrix <span class="math-container">$A$</span> with entries in <span class="math-container">$\{0,1\}$</span>, and given <span class="math-container">$k\ge 0$</span>, does <span class="math-container">$Per(A)=k$</span>?</p>
<p><strong>Question:</strong> Is it known to be NP-hard?  Should one expect this problem to be in C<span class="math-container">$_{=}$</span>P-complete?  (or maybe this is also already known?)</p>
<p>P.S.  I might be naive and this is super easy, but excessive googling did not show anything.</p>

CC BY-SA 4.0
2023-06-30T05:35:04.963Z
Hmm. It’s $\mathrm{C_=P}$-complete for $\{-1,0,1\}$-matrices (and for general integer matrices, of course).
Emil Jeřábek
CC BY-SA 4.0
2023-06-30T12:58:02.283Z
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.
Bruno
CC BY-SA 4.0
2023-06-30T13:49:21.930Z
@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$.
Emil Jeřábek
CC BY-SA 4.0
2023-06-30T20:38:15.993Z
@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?
Bruno
CC BY-SA 4.0
2023-07-01T06:26:41.753Z
@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.
Emil Jeřábek
<np-hardness><co.combinatorics><complexity-classes><counting-complexity><permanent>
Complexity of permanent verification
Igor Pak
# Complexity of permanent verification

(Asked by: username_0 on 2023-06-29)

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.

**Tags:** np-hardness, co.combinatorics, complexity-classes, counting-complexity, permanent

> **Comments:**
> **username_1**: Hmm. It’s $\mathrm{C_=P}$-complete for $\{-1,0,1\}$-matrices (and for general integer matrices, of course).  
> **username_2**: 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.  
> **username_1**: @username_2 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$.  
> **username_2**: @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?  
> **username_1**: @username_2 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.  

---

## 1 answers

### Answer by username_3 on 2023-07-03. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_4**: 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.  
> **username_0**: Thanks, Ryan!  This is very helpful.  

---

