For each #$k$SAT instance one can build a matrix $A$ such that $\mathrm{perm}(A) = F(\Sigma)$, where $\Sigma$ is the solution count of the $k$SAT formula and $F$ an easy to invert function.

My question is whether there is a similar reduction in the opposite direction: given an integer valued matrix $A$ with $\mathrm{perm}(A)>0$, is there a systematic way to build a #$k$SAT formula such that $\Sigma=F(\mathrm{perm}(A))$, where $F$ an easy to invert function?

  • 1
    $\begingroup$ If the entries of $A$ are nonnegative, then yes, just because #kSAT is #P-complete and perm of nonnegative integer matrices is in #P. If you allow negative entries, this seems closely related to GapP vs #P. $\endgroup$ May 18, 2019 at 3:16
  • $\begingroup$ @JoshuaGrochow What if I have negative entries but I am somehow guaranteed that $\mathrm{perm}(A)>0$? Also, how does the reduction in the case of only nonnegative entries? $\endgroup$
    – delete000
    May 18, 2019 at 12:36


Your Answer

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