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

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

CC BY-SA 4.0
2019-05-18T03:16:02.220Z
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.
Joshua Grochow
CC BY-SA 4.0
2019-05-18T12:36:20.030Z
@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?
delete000
<sat><counting-complexity><reductions><permanent>
Given $n\times n$ matrix $A$ with integer entries, find #$k$SAT formula that yields $\mathrm{perm}(A)>0$
delete000
# Given $n\times n$ matrix $A$ with integer entries, find #$k$SAT formula that yields $\mathrm{perm}(A)>0$

(Asked by: username_0 on 2019-05-13)

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?

**Tags:** sat, counting-complexity, reductions, permanent
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  

---

## 0 answers

