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$ – Joshua Grochow May 18 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 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.