9
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Hmm. It’s $\mathrm{C_=P}$-complete for $\{-1,0,1\}$-matrices (and for general integer matrices, of course). $\endgroup$
    – Emil Jeřábek
    Commented Jun 30, 2023 at 5:35
  • $\begingroup$ 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. $\endgroup$
    – Bruno
    Commented Jun 30, 2023 at 12:58
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Emil Jeřábek
    Commented Jun 30, 2023 at 13:49
  • $\begingroup$ @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? $\endgroup$
    – Bruno
    Commented Jun 30, 2023 at 20:38
  • $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Commented Jul 1, 2023 at 6:26

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – holf
    Commented Jul 3, 2023 at 21:03
  • 1
    $\begingroup$ Thanks, Ryan! This is very helpful. $\endgroup$
    – Igor Pak
    Commented Jul 5, 2023 at 1:31

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.