XOR-SAT to Horn-SAT reduction 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.
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). Thus using a division free determinant algorithm (e.g. by Mahajan-Vinay) 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.