Does anyone know of a non-trivial reduction from XORSAT to 2-sat since they are both in P? (By non-trivial I mean one that does not just solve the instance of XORSAT and map it to a fixed instance of 2-sat. Rather I'm looking for a way to solve XORSAT by a different method other than just using Gaussian Elimination or some other method of linear algebra.)

  • $\begingroup$ XORSAT defined on wikipedia $\endgroup$ – vzn Jun 22 '15 at 23:27

Your problem can be posed more formally as follows: Is there a weak reduction from XORSAT to 2SAT? Here weak can be, for example, logspace or AC$^0$.

We know that 2SAT is NL-complete under AC$^0$ reductions, while restricted versions of XORSAT (say 3XORSAT) are $\oplus$L-complete under AC$^0$ reductions, see this paper proving a refined Schaefer dichotomy theorem. Although NL$\subseteq \oplus$L non-uniformly (see this answer), we don't expect the converse to hold, and in particular we don't expect there to be a weak reduction from $\oplus$L to NL. Unfortunately I'm unaware of any concrete results in this direction.

Summarizing, it is expected that there is no weak reduction from XORSAT to 2SAT, but I'm not sure there's much technical work supporting this conjecture.

  • $\begingroup$ Thank you for your answer (although it is way too technical for me- I'm just a novice) I was actually just wondering if there are any other known algorithms for XORSAT other than interpreting it as a system of linear equations mod 2. I ask this since according to my limited knowledge, we know of different algorithms for 2sat and Horn-sat. Thanks again. $\endgroup$ – Ari Jul 16 '14 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.