Is #k-XORSAT #P-complete? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T02:24:53Z http://mathoverflow.net/feeds/question/35590 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35590/is-k-xorsat-p-complete Is #k-XORSAT #P-complete? András Salamon 2010-08-14T19:21:35Z 2011-04-05T10:44:27Z <p>k-XORSAT is the problem of deciding whether a Boolean formula $$\bigwedge_{i \in I} \oplus_{j=1}^k l_{s_{ij}}$$ is satisfiable. Here $\oplus$ denotes the binary <a href="http://en.wikipedia.org/wiki/Xor" rel="nofollow">XOR</a> operation, $I$ is some index set, and each clause has $k$ distinct literals $l_{s_{ij}}$ each of which is either a variable $x_{s_{ij}}$ or its negation.</p> <p>Equivalently, $k$-XORSAT requires deciding whether a set of linear equations, each of the form $\sum_{j=1}^k x_{s_{ij}}\equiv 1\; (\mod 2)$, has a solution over $\mathbb{Z}_2 = \mathbb{Z}/2\mathbb{Z}$.</p> <p>Every decision problem Q has an associated counting problem #Q, which (informally speaking) requires establishing the number of distinct solutions. Such counting problems form the complexity class <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3ASymbols#sharpp" rel="nofollow">#P</a>. The "hardest" problems in #P are #P-complete, as any problem in #P can be reduced to a #P-complete problem.</p> <p>The counting problem associated with any NP-complete decision problem is #P-complete. However, many "easy" decision problems (some even solvable in linear time) also lead to #P-complete counting problems. For instance, Leslie Valiant's original 1979 paper <a href="http://dx.doi.org/10.1016/0304-3975%2879%2990044-6" rel="nofollow"><em>The Complexity of Computing the Permanent</em></a> shows that computing the permanent of a 0-1 matrix is #P-complete. As a second example, the list of #P-complete problems in the companion paper <a href="http://dx.doi.org/10.1137/0208032" rel="nofollow"><em>The Complexity of Enumeration and Reliability Problems</em></a> includes #MONOTONE 2-SAT; this problem requires counting the number of solutions to Boolean formulas in conjunctive normal form, where each clause has two variables and no negated variables are allowed. (MONOTONE 2-SAT is of course rather trivial as a decision problem.)</p> <p>Andrea Montanari has written about the partition function of $k$-XORSAT in some <a href="http://www.stanford.edu/~montanar/TEACHING/Stat316/handouts/lecture-4.pdf" rel="nofollow">lecture notes</a>, and his book with Marc Mézard apparently discusses this (unfortunately I do not have a copy available to hand, and the relevant Chapter 17 is not included in Montanari's online draft).</p> <p>These considerations lead to the following question:</p> <blockquote> <p>Is #$k$-XORSAT #P-complete?</p> </blockquote> <p>Note that the formula in Montanari's notes does not obviously appear to answer this question. Just because there is a nice closed form solution, doesn't mean we can evaluate it efficiently: consider the <a href="http://en.wikipedia.org/wiki/Tutte_polynomial" rel="nofollow">Tutte polynomial</a>.</p> <p>Some difficult counting problems in #P can still be approximated in a certain sense, by means of a scheme called an FPRAS. Jerrum, Sinclair, and collaborators have linked the existence of an FPRAS for #P problems to the question of whether $NP = RP$. I would therefore also be interested in the subsidiary question</p> <blockquote> <p>Does #$k$-XORSAT have an FPRAS?</p> </blockquote> <p><em>Edit: clarified second question as per comment by Tsuyoshi Ito. Note that Peter Shor's answer renders this part of the question moot.</em></p> http://mathoverflow.net/questions/35590/is-k-xorsat-p-complete/35595#35595 Answer by Peter Shor for Is #k-XORSAT #P-complete? Peter Shor 2010-08-14T19:49:51Z 2010-09-07T15:11:20Z <p>The solutions for XOR-SAT form an affine subspace of the vector space GF(2)$^n$. You can see this by realizing that if you add three solutions together, you get another solution. The counting problem for XOR-SAT is then that of deciding how many points are in this affine space over GF(2). This is trivial if you know the rank of a generating matrix for this space (the number is $2^r$ for rank $r$). This rank can be figured out by a standard linear algebra algorithm, so the counting problem is in polynomial time.</p> http://mathoverflow.net/questions/35590/is-k-xorsat-p-complete/35733#35733 Answer by Andrea Montanari for Is #k-XORSAT #P-complete? Andrea Montanari 2010-08-16T07:23:12Z 2010-08-16T07:23:12Z <p>FYI: In our book we explain that the number of solutions of $Ax=b$ is $2^{n-rank(A)}$ as mentioned by Peter.</p>