0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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, 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

0

Reset to default

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.