Re: Can I solve 1-in-3 3-SAT in polynomial time?

In message <9f4ce534-739c-4cca-a5ce-355fbf0bbd9c@xxxxxxxxxxxxxxxxxxxxx
ups.com>
"soos.mate" <soos.mate@xxxxxxxxx> wrote:

Let us be given an arbitrary 1-in-3 3-SAT problem. Finding if it is
SAT or UNSAT is of course NP-complete. I write down the clauses:

(x_1, not x_2, not x_3)

as:

x_1+1-x_2+1-x_3=1

I now have a linear set of equations that I can solve with simple
Gaussian elimination. There are the following cases now:
[...]
4) The number of linearly independent equations is not enough. Some of
the variables are now defined. The rest can be chosen as pleased. The
solution is SAT.

Is it? How do you know that there is a solution with x_i in {0,1}?
It is clear that if the set of equations has no solution then the
original problem is not satisfiable, but most solutions to the set of
equations are not valid solutions to your original problem.

Martin
.