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!
3
-
$\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
Add a comment
|
$\begingroup$
$\endgroup$
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.
