18
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 14, 2010 at 20:51
  • $\begingroup$ Thank you for highlighting this, have edited the question so it makes more sense. $\endgroup$
    – András Salamon
    Commented Aug 15, 2010 at 14:13

2 Answers 2

Reset to default
28
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Sorry for the stupid question, but does this immediately imply that k-XORSAT is not #P-complete? $\endgroup$
    – Qiaochu Yuan
    Commented Aug 14, 2010 at 20:14
  • $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Aug 14, 2010 at 20:35
  • 4
    $\begingroup$ @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! $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 14, 2010 at 20:40
  • $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Aug 14, 2010 at 20:53
  • $\begingroup$ I'll edit the question to remove this source of confusion. $\endgroup$
    – András Salamon
    Commented Aug 14, 2010 at 21:00
4
$\begingroup$

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

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .