Re: Questions about Parity SAT

On Jan 16, 8:46 am, Finder <a_plakh...@xxxxxxx> wrote:
Hi everyone,

I've constructed a way to reduce Parity SAT (that is, the question
whether a SAT instance has an odd number of satisfying assignments; a
complete problem for Parity P if I'm not mistaken) to its special case
(which looks much easier) in polynomial time and space.

The special case, which I'll here denote "Parity SAT Positive", is the
same question about SAT instances where all literals are positive
(i.e. every clause doesn't contain negations).

Such a CNF formula is sometimes called a "monotone" formula, as it
represents a monotone function.
So another name for your problem would be "Parity MONOTONE SAT".

A recent survey by Valiant (in the proceedings of COCOON 2005) already
gives a proof that Parity MONOTONE SAT is Parity-P complete. However,
if your result continued to hold in a more special case then it would
be very interesting, resolving an open problem in the area. Valiant
states that certain parity problems are still open, in particular it
is not known if any of the following are Parity-P complete:

1. Parity 2-SAT,
2. Parity MONOTONE SAT but each variable has only two occurrences in
the formula,
3. Parity 3-SAT but each variable has only two occurrences.

The above reference should get you started. You may find it here

http://www.springerlink.com/content/3xa3b8a7cxy085dw/

or perhaps by googling for it.
Also, if your proof is much simpler than Valiant's, that may also be
interesting.

-ryan
.