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

Hi!

I cannot believe something, and I ask your help to find the flow in
the following reasoning.

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:

1) There is at least one line in the augmented matrix that appears
during the Gaussian elimination that has the form "0000..01000X" where
X is different from 1 or 0. The solution is UNSAT.

2) The number of linearly independent equations is enough and the
solution found fits the rest of the equations (I call the "rest" the
equations that were not used to make the augmented matrix). The
solution is SAT.

3) The number of linearly independent equations is enough and the
solution found does not fit at least one of the rest of the equations.
The solution is UNSAT.

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.

Naturally, 1) is taken to be of the highest priority, 4) lowest. I
cannot find the fallacy... Could anybody please enlighten me?

Thank you in advance,

Mate
.

Quantcast