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!
-1
closed as unclear what you're asking by David Richerby, Evil, Apass.Jack, Kyle Jones, Juho Nov 8 '18 at 8:52
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
-
$\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
1
$\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.
