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$
$\endgroup$
1
-
$\begingroup$ XORSAT defined on wikipedia $\endgroup$– vznJun 22, 2015 at 23:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
answered Jul 15, 2014 at 21:19
-
$\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$– AriJul 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$– TurboJun 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$– TurboJun 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