# Re: Questions about Parity SAT

*From*: Finder <a_plakhoff@xxxxxxx>*Date*: Fri, 18 Jan 2008 06:44:50 -0800 (PST)

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

Hi,Yes, exactly.

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?

This reduction may be interesting but I do doubt that it is correct. If youIt's too bulky to describe it here (and using plain text only). I'll

have described your idea than maybe someone would point where is a flaw.

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.You seem to be wrong: (F or r) has exactly the same SAT-parity as 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.

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

.

**Follow-Ups**:**Re: Questions about Parity SAT***From:*Radoslaw Hofman

**References**:**Questions about Parity SAT***From:*Finder

**Re: Questions about Parity SAT***From:*Radoslaw Hofman

- Prev by Date:
**Re: Questions about Parity SAT** - Next by Date:
**Re: Could anyone help me with this math problem please?** - Previous by thread:
**Re: Questions about Parity SAT** - Next by thread:
**Re: Questions about Parity SAT** - Index(es):