# How many solutions are there for a XOR-SAT formula? [closed]

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!

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

However;

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