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, 2015 at 23:27

1 Answer 1


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, 2014 at 13:47
  • $\begingroup$ @yuvalfilmus is $kxorsat$ the version of sat where every clause has atmost k variables and the clauses are of type $a_1\oplus\dots\oplus a_m\equiv1\bmod 2$ where $1\leq m\leq k$ and $a_i\in\{x_1,\overline{x_1},\dots,x_n,\overline{x_n}\}$? Is there a reference for proof for the version of sat being $\oplus L$ complete? $\endgroup$
    – Turbo
    Jun 2, 2021 at 11:19
  • $\begingroup$ @BreadWinner people.cs.umass.edu/~immerman/pub/cspJCSS.pdf $\endgroup$ Jun 2, 2021 at 11:34
  • $\begingroup$ @yuvalfilmus I think relevant portion is L2,L3 in diagram and theorem 3.1. it states a definition of clone which is not clear. Why is the clone terminology important? $\endgroup$
    – Turbo
    Jun 2, 2021 at 12:42
  • $\begingroup$ On the bottom paragraph of page 3 you can find some references for standard terminology in universal algebra used in this paper. These concepts are important since the polymorphisms of $\Gamma$ determine the complexity of $\mathrm{CSP}(\Gamma)$, as Theorem 3.1 shows. $\endgroup$ Jun 2, 2021 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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