Re: Questions about Parity SAT

Le 23-01-2008, Radoslaw Hofman <radekh@xxxxxxxxx> a écrit :
Imagine we have some SAT (ordinary) instance. Let us denote it as
formula F.
[...]


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.


I don't think you have patched your idea correctly. As you say the
new formula always has 2s satisfying assignments, so it is never odd.
What you want is a new formula with 2^s satisfying assignments.



Best regards,



Radek Hofman


.