Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 XOR 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.

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}$.

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 #P. The "hardest" problems in #P are #P-complete, as any problem in #P can be reduced to a #P-complete problem.

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 The Complexity of Computing the Permanent 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 The Complexity of Enumeration and Reliability Problems 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.)

Andrea Montanari has written about the partition function of $k$-XORSAT in some lecture notes, 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).

These considerations lead to the following question:

Is #$k$-XORSAT #P-complete?

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 Tutte polynomial.

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

Does #$k$-XORSAT have an FPRAS?

Edit: clarified second question as per comment by Tsuyoshi Ito. Note that Peter Shor's answer renders this part of the question moot.

share|improve this question
2  
Note that some #P-complete problems (e.g. the DNF counting problem) have an FPRAS. Therefore, the #P-completeness does not rule out the existence of an FPRAS. –  Tsuyoshi Ito Aug 14 '10 at 20:51
    
Thank you for highlighting this, have edited the question so it makes more sense. –  András Salamon Aug 15 '10 at 14:13

2 Answers 2

up vote 22 down vote accepted

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.

share|improve this answer
    
Thanks for the elegant argument! –  András Salamon Aug 14 '10 at 19:53
1  
Sorry for the stupid question, but does this immediately imply that k-XORSAT is not #P-complete? –  Qiaochu Yuan Aug 14 '10 at 20:14
    
The way I understand Peter's answer, yes: compute the rank $r$ of the system, then the answer is $2^r$. As the rank is at most $k$, a constant, this can be computed in polynomial time. –  András Salamon Aug 14 '10 at 20:35
3  
@Qiaochu: Peter’s answer explains how to compute the number of the solutions to any given instance of the XORSAT problem in polynomial time (and k-XORSAT is a special case of XORSAT). Therefore, yes, it implies that the counting version of k-XORSAT is not #P-complete — unless the whole #P is computable in polynomial time! –  Tsuyoshi Ito Aug 14 '10 at 20:40
    
Ah, thanks. I was confused by the remark about problems solvable in linear time leading to #P-complete problems, but now I see that the remark was about problems whose decision versions are solvable in linear time and whose counting versions are #P-complete. –  Qiaochu Yuan Aug 14 '10 at 20:53

FYI: In our book we explain that the number of solutions of $Ax=b$ is $2^{n-rank(A)}$ as mentioned by Peter.

share|improve this answer
    
I'll definitely be picking up a copy. But the draft online seems to miss out Chapter 17... –  András Salamon Aug 16 '10 at 14:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.