<p>$\def\F{\mathbb F_2}\let\ET\bigwedge$Let me convert my old comment above to a proper answer, as it is a <em>much</em> simpler construction than in the other answer.</p>

<p>XOR-SAT can be computed in polynomial time by Gaussian elimination. Thus, it is reducible to Horn-SAT. The reduction amounts to describing the local conditions for correctness of a transcript of a run of the Gaussian elimination algorithm, and with a reasonable representation of the output, it can be made a DLogTime reduction.</p>

<p>In fact, Gaussian elimination is simple enough that a (slightly optimized) reduction can be described completely explicitly. Assume that we are given a matrix $A=(a_i^j)\in\F^{m\times(n+1)}$, representing the linear system
$$\begin{align*}
a_1^1x_1+\dots+a_n^1x_n&amp;=a_{n+1}^1\\
\tag{L}\vdots\\
a_1^mx_1+\dots+a_n^mx_n&amp;=a_{n+1}^m
\end{align*}$$
over $\F$. We will produce a system (H) of Horn clauses such that (L) is solvable iff (H) is satisfiable. The definition of (H) will simulate the following version of Gaussian elimination over $\F$:</p>

<blockquote>
  <p>while $A\ne0$ do:</p>
  
  <blockquote>
    <p>if some row has a unique nonzero entry in its $(n+1)$th column: REJECT</p>
    
    <p>let $p$ be the first nonzero column of $A$</p>
    
    <p>let $q$ be the first nonzero entry in column $p$</p>
    
    <p>add row $q$ to all rows of $A$ with nonzero entry in column $p$</p>
  </blockquote>
  
  <p>ACCEPT</p>
</blockquote>

<p>Note that the pivot row in particular gets added to itself, which zeroes it out (we won’t need it any more). Since each iteration kills at least one column, the loop will iterate at most $n$ times.</p>

<p>Now, the Horn system (H) uses variables
$$y_{t,i,j,a}\qquad(0\le t\le n;1\le i\le n+1;1\le j\le m;a\in\F)$$
with the intended meaning “after $t$ iterations, the $(i,j)$th entry of $A$ has value $a$”. The system consists of the “initial” clauses
$$y_{0,i,j,a_i^j}\tag1$$
for $1\le i\le n+1$ and $1\le j\le m$; the negative “rejection” clauses
$$\ET_{i=1}^ny_{t,i,j,0}\to\neg y_{t,n+1,j,1}\tag2$$
for $0\le t\le n$ and $1\le j\le m$; and the “next iteration” clauses
$$\ET_{i=1}^{p-1}\ET_{j=1}^my_{t,i,j,0}\land\ET_{j=1}^{q-1}y_{t,p,j,0}\land y_{t,p,q,1}\land y_{t,k,l,a}\land y_{t,p,l,b}\land y_{t,k,q,c}\to y_{t+1,k,l,a+bc}\tag3$$
for $0\le t&lt;n$, $1\le p\le n$, $1\le q\le m$, $1\le k\le n+1$, $1\le l\le m$, and $a,b,c\in\F$.</p>

<p>It should be clear from the discussion that (H) is equisatisfiable with (L).</p>

CC BY-SA 3.0
2016-10-31T14:56:43.180Z
2016-10-31T15:58:56.467Z
2016-10-31T15:58:56.467Z
Emil Jeřábek
<p>XOR-SAT is in $\mathsf{L}^{\oplus\mathsf{L}} = \oplus\mathsf{L}$ (because it can be viewed as the feasibility of a system of linear equations mod 2 hence by <a href="http://ftp.cs.rutgers.edu/pub/allender/rank.pdf" rel="noreferrer">Allender-Beals-Ogihara</a>). Thus using a division free determinant algorithm (e.g. by <a href="http://www.imsc.res.in/~meena/papers/cjtcs-det.ps.gz" rel="noreferrer">Mahajan-Vinay</a>) we can reduce it to the problem of iterated matrix product over $F_2$ by a finegrained reduction (certainly Log-space will work but something finer like Dlogtime projection should also). Now design an $\mathsf{NC}^2$ circuit to multiply together several matrices over $F_2$ using $\{\vee,\wedge,\neg\}$-gates. Thus composing the above reductions with the reduction from CVP to HornSAT gives the final reduction.</p>

CC BY-SA 3.0
2016-10-30T08:07:25.920Z
First of all thanks for the answer. I don’t understand the following case: if we have the simple _xor_ instance _a$\oplus$b_, which is the _Horn-SAT_ instance that is satisfiabile iff _a_ and _b_ have opposite truth values (_a$\oplus$b_ is false if _a_ and _b_ have the same truth value)?
Mario Giambarioli
CC BY-SA 3.0
2016-10-30T08:12:50.853Z
@MarioGiambarioli I don't know off-hand but you can work through the chain of reductions to obtain the actual HornSAT formula.
SamiD
CC BY-SA 3.0
2016-10-30T08:31:59.337Z
Ok, but in the _a$\oplus$b_ case we have only one equation _a$\oplus$b=1_ (not a system of equations), then we have a matrix with only one row, therefore there isn’t a determinant neither a rank (the rank is 1). So I don’t know how to apply the chain of reductions that you say.
Mario Giambarioli
CC BY-SA 3.0
2016-10-30T08:41:33.553Z
True. This is the answer. Since the formula you mention is satisfiable.
SamiD
CC BY-SA 4.0
2018-06-29T23:42:28.883Z
The part at the beginning about XOR-SAT being in parity-L.  Is this a known result?  Also, when I went through the paper that you link (which is great and directly relevant), I couldn't quite figure out how to apply their result to get that XOR-SAT is in parity-L.  Would you be willing to explain more about this?  Thank you very much for all of your help!!  :)
Michael Wehar
CC BY-SA 4.0
2018-06-30T00:57:14.047Z
I found this which seems to resolve my question: 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
2021-06-02T07:48:18.800Z
@MichaelWehar I am not understanding in correct manner. Is $XORSAT$ in $\oplus L$ and is it $\oplus L$ complete?
Turbo
CC BY-SA 4.0
2021-06-02T11:09:28.067Z
@MichaelWehar in general is $kxorsat$ where every clause is a parity constraint on atmost $k$ variables $mod_kL$ or $comod_kL$ complete?
Turbo
CC BY-SA 3.0
2016-10-28T11:43:41.493Z
2016-10-28T11:43:41.493Z
SamiD
<p><em>Horn-SAT</em> (conjunction of <em>Horn</em> clauses) is <strong>P-complete</strong> and <em>XOR-SAT</em> (conjunction of <em>xor</em> clauses) is in <strong>P</strong>. This means that there is a reduction from <em>XOR-SAT</em> to <em>Horn-SAT</em> weaker than a polynomial reduction.
I am looking for such a reduction; can anyone help me? Thank you.</p>

CC BY-SA 3.0
2016-10-03T00:35:21.273Z
Given an instance of XOR-SAT, solve the instance in polynomial time and then produce the Horn-SAT instance $(a \rightarrow a)$ if it was satisfiable and the instance $(\neg a \rightarrow a) \wedge (a \rightarrow \neg a)$ otherwise. The same can be done for any replacement of Horn-SAT with a language $L \not \in \{\emptyset, \Sigma^*\}$.
Yonatan N
CC BY-SA 3.0
2016-10-03T05:47:18.910Z
So, the right question is to give a more efficient kind of reduction, say, logspace, FO, or even logtime. The straightforward answer is to describe the computation of a Gaussian elimination algorithm by Horn clauses, which is going to be fairly unsightly. So, the right right question is if we can find something simpler.
Emil Jeřábek
CC BY-SA 3.0
2016-10-03T09:41:16.330Z
@EmilJeřábek Emil you are right, I am looking for a weaker reduction than a polynimial reduction (log-space or NC for example). If we use polynomial reduction, all problems in **P** are complete, as Wikipedia say [link](https://en.wikipedia.org/wiki/Polynomial-time_reduction)
Mario Giambarioli
CC BY-SA 4.0
2023-07-07T08:55:24.203Z
"weaker than a polynomial reduction". I suppose it is not just weaker than a polynomial reduction, but has to be actually a (deterministic) log-space reduction. If you allow stronger reductions (such as $NC$), you might find that some languages that (presumably) are not P-hard under log-space reductions become P-hard.
rus9384
<complexity-classes><circuit-complexity>
XOR-SAT to Horn-SAT reduction
Mario Giambarioli
# XOR-SAT to Horn-SAT reduction

(Asked by: username_0 on 2016-10-02)

*Horn-SAT* (conjunction of *Horn* clauses) is **P-complete** and *XOR-SAT* (conjunction of *xor* clauses) is in **P**. This means that there is a reduction from *XOR-SAT* to *Horn-SAT* weaker than a polynomial reduction.
I am looking for such a reduction; can anyone help me? Thank you.

**Tags:** complexity-classes, circuit-complexity
> **Comments:**
> **username_1**: Given an instance of XOR-SAT, solve the instance in polynomial time and then produce the Horn-SAT instance $(a \rightarrow a)$ if it was satisfiable and the instance $(\neg a \rightarrow a) \wedge (a \rightarrow \neg a)$ otherwise. The same can be done for any replacement of Horn-SAT with a language $L \not \in \{\emptyset, \Sigma^*\}$.  
> **username_2**: So, the right question is to give a more efficient kind of reduction, say, logspace, FO, or even logtime. The straightforward answer is to describe the computation of a Gaussian elimination algorithm by Horn clauses, which is going to be fairly unsightly. So, the right right question is if we can find something simpler.  
> **username_0**: @EmilJeřábek Emil you are right, I am looking for a weaker reduction than a polynimial reduction (log-space or NC for example). If we use polynomial reduction, all problems in **P** are complete, as Wikipedia say [link](https://en.wikipedia.org/wiki/Polynomial-time_reduction)  
> **username_3**: "weaker than a polynomial reduction". I suppose it is not just weaker than a polynomial reduction, but has to be actually a (deterministic) log-space reduction. If you allow stronger reductions (such as $NC$), you might find that some languages that (presumably) are not P-hard under log-space reductions become P-hard.  

---

## 2 answers

### Answer by username_2 on 2016-10-31. Score: 8

$\def\F{\mathbb F\_2}\let\ET\bigwedge$Let me convert my old comment above to a proper answer, as it is a *much* simpler construction than in the other answer.

XOR-SAT can be computed in polynomial time by Gaussian elimination. Thus, it is reducible to Horn-SAT. The reduction amounts to describing the local conditions for correctness of a transcript of a run of the Gaussian elimination algorithm, and with a reasonable representation of the output, it can be made a DLogTime reduction.

In fact, Gaussian elimination is simple enough that a (slightly optimized) reduction can be described completely explicitly. Assume that we are given a matrix $A=(a\_i^j)\in\F^{m\times(n+1)}$, representing the linear system
$$\begin{align\*}
a\_1^1x\_1+\dots+a\_n^1x\_n&=a\_{n+1}^1\\
\tag{L}\vdots\\
a\_1^mx\_1+\dots+a\_n^mx\_n&=a\_{n+1}^m
\end{align\*}$$
over $\F$. We will produce a system (H) of Horn clauses such that (L) is solvable iff (H) is satisfiable. The definition of (H) will simulate the following version of Gaussian elimination over $\F$:

> while $A\ne0$ do:
>
> > if some row has a unique nonzero entry in its $(n+1)$th column: REJECT
> >
> > let $p$ be the first nonzero column of $A$
> >
> > let $q$ be the first nonzero entry in column $p$
> >
> > add row $q$ to all rows of $A$ with nonzero entry in column $p$
>
> ACCEPT

Note that the pivot row in particular gets added to itself, which zeroes it out (we won’t need it any more). Since each iteration kills at least one column, the loop will iterate at most $n$ times.

Now, the Horn system (H) uses variables
$$y\_{t,i,j,a}\qquad(0\le t\le n;1\le i\le n+1;1\le j\le m;a\in\F)$$
with the intended meaning “after $t$ iterations, the $(i,j)$th entry of $A$ has value $a$”. The system consists of the “initial” clauses
$$y\_{0,i,j,a\_i^j}\tag1$$
for $1\le i\le n+1$ and $1\le j\le m$; the negative “rejection” clauses
$$\ET\_{i=1}^ny\_{t,i,j,0}\to\neg y\_{t,n+1,j,1}\tag2$$
for $0\le t\le n$ and $1\le j\le m$; and the “next iteration” clauses
$$\ET\_{i=1}^{p-1}\ET\_{j=1}^my\_{t,i,j,0}\land\ET\_{j=1}^{q-1}y\_{t,p,j,0}\land y\_{t,p,q,1}\land y\_{t,k,l,a}\land y\_{t,p,l,b}\land y\_{t,k,q,c}\to y\_{t+1,k,l,a+bc}\tag3$$
for $0\le t

It should be clear from the discussion that (H) is equisatisfiable with (L).


---

### Answer by username_4 on 2016-10-28. Score: 5

XOR-SAT is in $\mathsf{L}^{\oplus\mathsf{L}} = \oplus\mathsf{L}$ (because it can be viewed as the feasibility of a system of linear equations mod 2 hence by [Allender-Beals-Ogihara](http://ftp.cs.rutgers.edu/pub/allender/rank.pdf)). Thus using a division free determinant algorithm (e.g. by [Mahajan-Vinay](http://www.imsc.res.in/~meena/papers/cjtcs-det.ps.gz)) we can reduce it to the problem of iterated matrix product over $F\_2$ by a finegrained reduction (certainly Log-space will work but something finer like Dlogtime projection should also). Now design an $\mathsf{NC}^2$ circuit to multiply together several matrices over $F\_2$ using $\{\vee,\wedge,\neg\}$-gates. Thus composing the above reductions with the reduction from CVP to HornSAT gives the final reduction.

> **Comments:**
> **username_0**: First of all thanks for the answer. I don’t understand the following case: if we have the simple _xor_ instance _a$\oplus$b_, which is the _Horn-SAT_ instance that is satisfiabile iff _a_ and _b_ have opposite truth values (_a$\oplus$b_ is false if _a_ and _b_ have the same truth value)?  
> **username_4**: @MarioGiambarioli I don't know off-hand but you can work through the chain of reductions to obtain the actual HornSAT formula.  
> **username_0**: Ok, but in the _a$\oplus$b_ case we have only one equation _a$\oplus$b=1_ (not a system of equations), then we have a matrix with only one row, therefore there isn’t a determinant neither a rank (the rank is 1). So I don’t know how to apply the chain of reductions that you say.  
> **username_4**: True. This is the answer. Since the formula you mention is satisfiable.  
> **username_5**: The part at the beginning about XOR-SAT being in parity-L.  Is this a known result?  Also, when I went through the paper that you link (which is great and directly relevant), I couldn't quite figure out how to apply their result to get that XOR-SAT is in parity-L.  Would you be willing to explain more about this?  Thank you very much for all of your help!!  :)  
> **username_5**: I found this which seems to resolve my question: https://cstheory.stackexchange.com/questions/8936/is-solving-systems-of-equations-modulo-k-in-mathsfcomod-k-mathsf-l-for-k  :)  
> **username_6**: @MichaelWehar I am not understanding in correct manner. Is $XORSAT$ in $\oplus L$ and is it $\oplus L$ complete?  
> **username_6**: @MichaelWehar in general is $kxorsat$ where every clause is a parity constraint on atmost $k$ variables $mod_kL$ or $comod_kL$ complete?  

---

