Does anyone know how many solutions there are for a XOR-SAT formula? And how do the variables in solutions distribute? For example, if (x0=1, x1=0, x2=1) is a solution for a XOR-SAT formula, how does x0 distribute in different solutions? Thanks!

  • $\begingroup$ Depends on the instance of the problem. You solve it, by converting linear equations equal to 1 and than using Gaussian elimination. $\endgroup$ – kelalaka Nov 3 '18 at 9:14
  • $\begingroup$ The number of solutions depends on the formula, so it's not really clear what you're asking. $\endgroup$ – David Richerby Nov 3 '18 at 11:31
  • $\begingroup$ What do you mean by "distribute"? Could you please give a formal definition? $\endgroup$ – xskxzr Nov 3 '18 at 12:12

The answer depends on the instance of the problem; For example;

$$(x_0 \oplus x_1) \wedge (x_0 \oplus \neg x_1)$$ has no solution at all.


$$(x_0 \oplus x_1) \wedge (x_0 )$$ has solutions.

Finding the solutions, or the inconsistency is not that hard. You convert the problem into a linear system of equations as;

$$(x_0 + x_1) \equiv 1 \mod 2, \text{ and }$$$$ (x_0 + (1 + x_1)) \equiv 1 \mod 2 $$

and than the problem can be solved by the Gaussian elimination.


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