Re: Questions about Parity SAT

On Jan 18, 2:24 pm, "Radoslaw Hofman" <rad...@xxxxxxxxx> wrote:
Hi,

I am not sure if I've got it right. Your "Parity SAT Positive" is an SAT
instance where each literal exists only in its non-negated form in each
clause it appears? What means that if each clause contains at least one
literal the expression is satisfied?
Yes, exactly.

This reduction may be interesting but I do doubt that it is correct. If you
have described your idea than maybe someone would point where is a flaw.
It's too bulky to describe it here (and using plain text only). I'll
test it myself during some more days (both the proof and the
algorithm's implementation on the PC) to figure out if it has a flaw.

Imagine we have some SAT (ordinary) instance. Let us denote it as formula F.
Problem question is "Is there at least one assignment". So we create another
instance using brand new (not existing in F) literal r, and ask question if
new formula: (F or r) has odd number of assignments? If we could correctly
answer this question then at the same time we will have answer to our
original SAT instance.
You seem to be wrong: (F or r) has exactly the same SAT-parity as F,
which may be zero for satisfiable instances. But if Parity SAT is in
P, then NP-hard problems are in RP according to Valiant-Vazirani
theorem. This would be extremely interesting too. I don't know fast
algorithms for Parity SAT Positive (in fact, everything I can think of
is something resembling DPLL) - but it looks much simpler than Parity
SAT.

Kind Regards,
Andy
.