<p>Take a look at <a href="https://www.sciencedirect.com/science/article/pii/S0022000008001141" rel="noreferrer">https://www.sciencedirect.com/science/article/pii/S0022000008001141</a> "The complexity of satisfiability problems: Refining Schaefer's theorem" by Allender et al. which answer your questions:</p>

<p>(1) Open</p>

<p>(2) $\oplus L = L$</p>

<p>(3) Yes</p>

CC BY-SA 4.0
2018-06-30T13:10:42.967Z
Thank you so much!!  This is exactly what I wanted!!  I didn't initially realize that we could reduce XOR SAT to XOR 3-SAT using the same trick as we do for reducing CNF SAT to CNF 3-SAT.  Also, reference [28] from the paper that you linked explains why XOR SAT is $\oplus L$ complete.
Michael Wehar
CC BY-SA 4.0
2018-06-30T11:04:23.213Z
2018-06-30T11:04:23.213Z
Gustav Nordh
<p><strong>XOR Formulas</strong></p>

<p>Consider boolean formulas with connectives $\wedge$ (AND) and $\oplus$ (XOR).  Such a boolean formula is a valid instance for XOR SAT if it is a conjunction of $\oplus$-clauses.  An $\oplus$-clause contains literals that are connected with $\oplus$.</p>

<p><strong>Example Formula:</strong></p>

<p>$(v_1 \oplus \bar{v_2} \oplus v_3 \oplus v_4) \wedge (\bar{v_1} \oplus v_2) \wedge (\bar{v_2} \oplus v_3 \oplus \bar{v_4})$</p>

<p><strong>Decision Problem</strong></p>

<blockquote>
  <p><strong>Name:</strong> XOR 3-SAT</p>
  
  <p><strong>Input:</strong> A boolean formula that is a conjunction of $\oplus$-clauses where each clause contains three literals.</p>
  
  <p><strong>Question:</strong> Does there exist an assignment to the variables that satisfies the formulas?</p>
</blockquote>

<p><strong>More Background</strong></p>

<p>XOR SAT can be reduced to solving a system of equations over $\mathbb{Z}_2$.  This is because every $\oplus$-clause can be thought of as an equation.  As a result, XOR SAT is solvable in polynomial time using gaussian elimination.</p>

<p>Further, XOR 2-SAT can be reduced to solving reachability in an undirected graph.  This is because every $\oplus$-clause with two literals defines an edge in an undirected graph.  As a result, XOR 2-SAT is solvable in logspace because reachability in an undirected graph is solvable in logspace (because SL = L).</p>

<p><strong>Question</strong></p>

<blockquote>
  <p>(1) Is XOR 3-SAT solvable in logspace?</p>
  
  <p>(2) Are there any known consequences of solving XOR 3-SAT in logspace?</p>
  
  <p>(3) For example, would this imply that XOR $k$-SAT is solvable in
  logspace?</p>
</blockquote>

CC BY-SA 4.0
2018-06-30T00:14:23.813Z
A related post: https://cstheory.stackexchange.com/questions/36704/xor-sat-to-horn-sat-reduction/36876
Michael Wehar
CC BY-SA 4.0
2018-06-30T00:58:17.723Z
@user124864 I'm not entirely sure.
Michael Wehar
CC BY-SA 4.0
2018-06-30T00:58:31.137Z
I just found this which I think is relevant: https://cstheory.stackexchange.com/questions/8936/is-solving-systems-of-equations-modulo-k-in-mathsfcomod-k-mathsf-l-for-k
Michael Wehar
CC BY-SA 4.0
2018-06-30T12:24:47.357Z
There is an obvious reduction of XOR-SAT to XOR-3-SAT. Both problems are $\oplus L$-complete, hence you are simply asking about the consequences of $L=\oplus L$. Oh, and of course $\oplus L\subseteq NC^2\subseteq DSPACE((\log n)^2)$
Emil Jeřábek
<cc.complexity-theory><complexity-classes><sat><linear-algebra><logspace>
What are the consequences of solving XOR 3-SAT in Logspace?
Michael Wehar
# What are the consequences of solving XOR 3-SAT in Logspace?

(Asked by: username_0 on 2018-06-30)

**XOR Formulas**

Consider boolean formulas with connectives $\wedge$ (AND) and $\oplus$ (XOR). Such a boolean formula is a valid instance for XOR SAT if it is a conjunction of $\oplus$-clauses. An $\oplus$-clause contains literals that are connected with $\oplus$.

**Example Formula:**

$(v\_1 \oplus \bar{v\_2} \oplus v\_3 \oplus v\_4) \wedge (\bar{v\_1} \oplus v\_2) \wedge (\bar{v\_2} \oplus v\_3 \oplus \bar{v\_4})$

**Decision Problem**

> **Name:** XOR 3-SAT
>
> **Input:** A boolean formula that is a conjunction of $\oplus$-clauses where each clause contains three literals.
>
> **Question:** Does there exist an assignment to the variables that satisfies the formulas?

**More Background**

XOR SAT can be reduced to solving a system of equations over $\mathbb{Z}\_2$. This is because every $\oplus$-clause can be thought of as an equation. As a result, XOR SAT is solvable in polynomial time using gaussian elimination.

Further, XOR 2-SAT can be reduced to solving reachability in an undirected graph. This is because every $\oplus$-clause with two literals defines an edge in an undirected graph. As a result, XOR 2-SAT is solvable in logspace because reachability in an undirected graph is solvable in logspace (because SL = L).

**Question**

> (1) Is XOR 3-SAT solvable in logspace?
>
> (2) Are there any known consequences of solving XOR 3-SAT in logspace?
>
> (3) For example, would this imply that XOR $k$-SAT is solvable in
> logspace?

**Tags:** cc.complexity-theory, complexity-classes, sat, linear-algebra, logspace
> **Comments:**
> **username_0**: A related post: https://cstheory.stackexchange.com/questions/36704/xor-sat-to-horn-sat-reduction/36876  
> **username_0**: @user124864 I'm not entirely sure.  
> **username_0**: I just found this which I think is relevant: https://cstheory.stackexchange.com/questions/8936/is-solving-systems-of-equations-modulo-k-in-mathsfcomod-k-mathsf-l-for-k  
> **username_1**: There is an obvious reduction of XOR-SAT to XOR-3-SAT. Both problems are $\oplus L$-complete, hence you are simply asking about the consequences of $L=\oplus L$. Oh, and of course $\oplus L\subseteq NC^2\subseteq DSPACE((\log n)^2)$  

---

## 1 answers

### Answer by username_2 on 2018-06-30. Score: 13 | Accepted answer

Take a look at <https://www.sciencedirect.com/science/article/pii/S0022000008001141> "The complexity of satisfiability problems: Refining Schaefer's theorem" by Allender et al. which answer your questions:

(1) Open

(2) $\oplus L = L$

(3) Yes

> **Comments:**
> **username_0**: Thank you so much!!  This is exactly what I wanted!!  I didn't initially realize that we could reduce XOR SAT to XOR 3-SAT using the same trick as we do for reducing CNF SAT to CNF 3-SAT.  Also, reference [28] from the paper that you linked explains why XOR SAT is $\oplus L$ complete.  

---

