Re: Questions about Parity SAT

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.

Yes. After adding or we in fact (for s solutions) make them 2^n*s+s what
perserves parity.


I have proposed new version:

(F and ((a or b) and (not a or not b)))



If F has some number of solutions (s), then this new formula has 2*s
solutions. If you have answered question "if this new formula has odd number
of assignments" positively then you would have also answered question "if F
has at least one assignment" what means SAT problem.



Best regards,



Radek Hofman


.