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

On May 26, 5:26 pm, Martin Wuerthner <spamt...@xxxxxxxxxxxxxxx> wrote:
In message <9f4ce534-739c-4cca-a5ce-355fbf0bb...@xxxxxxxxxxxxxxxxxxxxx
ups.com>
"soos.mate" <soos.m...@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.

So you agree that all other cases (1..3) can be solved with Gaussian
elimination? That sounds really strange :O

As for the 4th, here is my updated reasoning, which needed to be
refined, I agree. We all agree that there is no line in the augmented
matrix such as 00..0100..X where X is not 1 or 0. With permutation of
the columns of the non-augmented part of the matrix, we can always
arrive at the following:

100...0xxxxx|y1
010...0xxxxx|y2
001...0xxxxx|y3
000...1xxxxx|y4
000...0xxxxx|y5
....
000...0xxxxx|yn

where the parts that are marked "xxxxx" are not linearly independent
and might be different for each line. Let us divide all lines that
look like

"000...0 x x x x x ... x |y5"
=
"000...0 x1 x2 x3 x4 x5 ... xn |y"

by the smallest common divisor of all the numbers x1, x2, ..xn. If at
any point "y" becomes a number that is not an integer, the solution is
UNSAT. Let us assume that the last line's "xxxxx" is the smallest
common divisor of all the rest of the lines' "xxxxx". One "xxxxx" must
exists that has this property, otherwise they would not be lin.
indep. . I can now simply use the last line to get rid of the "xxxxx"
from all the rest of the matrix:

100...00000|y1-?*yn
010...00000|y2-?*yn
001...00000|y3-?*yn
000...10000|y4-?*yn
000...00000|y5-?*yn
....
000...xxxxxx|yn

We now need to check that all lines that contain a "1" to have their
last column be either 0 or 1, and the lines that do not contain any
"1" to have their last column as 0. If this check fails, we have
UNSAT. If it succeeds, then any solution that satisfies the last line
(these can be found in linear time) satisfies the original problem.
.

Relevant Pages

  • Re: linear independence of identity matrix vectors
    ... >>>gotten using linear combination of the rest. ... span do not have to be linearly independent. ... This explicitly shows a linear dependence of the vector ... on the standard basis vectors. ...
    (sci.math)
  • Re: Maximum number of linearly independent vectors
    ... are linearly independent. ... up "dimension of vector space", in linear algebra books (or in google, ... there's a theorem that says that every basis of R^n has ... that any set of 8 vectors in R^7 is linearly dependent? ...
    (sci.math)
  • Re: Are eigenvectors independent
    ... c1-ci is nonzero since by assumption all the ci are pairwise ... Let T be a linear operator on V, let c1,...,ck be pairwise ... that } is linearly independent. ... So you can find bases for the distinct eigenvalues, put them together, ...
    (sci.math)
  • Re: Question on sums of roots of integers
    ... Note that being linearly independent implies more ... linear combination of the other numbers. ... Ian J. Richards, ... to elementary arithmetic", Advances in Mathematics ...
    (sci.math)
  • Re: x^2 + y^2 + z^2 = r^2 + s^2 + t^2
    ... we can reduce the second of these to an elementary symmetric function: ... If we take t and z as unknowns, and r,s,x,y as parameters, this gives ... linear equations, which in turn solves the original problem. ... This gives all the solutions of the original problem. ...
    (sci.math)