# What are the consequences of solving XOR 3-SAT in Logspace?

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?

• A related post: cstheory.stackexchange.com/questions/36704/… Jun 30 '18 at 0:14
• @user124864 I'm not entirely sure. Jun 30 '18 at 0:58
• I just found this which I think is relevant: cstheory.stackexchange.com/questions/8936/… Jun 30 '18 at 0:58
• 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)$ Jun 30 '18 at 12:24

(2) $\oplus L = L$
• 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. Jun 30 '18 at 13:10