The Tseitin formulas are as follows: Given a connected graph and a function $\alpha: V \rightarrow \{0,1\}$. Associate each edge $e$ with a variable $x_e$. The Tseitin formula $G(\alpha)$ is defined to be $$ \bigwedge_{v \in V} \big(\sum_{(u,v) \in E(G)} x_{(u,v)} = \alpha(v) \mod 2 \big) $$

It's easy to see that the Tseitin formula $G(\alpha)$ is satisfiable iff $\sum_{v \in V} \alpha(v) = 0 \mod 2$.

This gives a nice characterization of the satisfiability of a system of random mod2 equations ($k$-XORs) $Ax = b \mod 2$ where each variable occurs in exactly 2 equations in the system which is connected (we cannot partition the rows of $A$ into two sets $A_1$ and $A_2$ so that $A_1 \cap A_2 = \emptyset$). Push the negation of any variable in a constraint into $b$ so that all variables occur positively in $A$. $Ax = b$ is then satisfiable iff $$\sum_{i = 1}^{|b|} b_i= 0 \mod 2.$$ This is because $Ax = b$ is equivalent to the Tseitin formulas where for each constraint $a_ix = b_i$ we create a vertex $v_i$ where $\alpha(v_i) = b_i$ and each variable $x_i$ corresponds to an edge between the two constraints in which $x_i$ appears.

My question is, if we relax the requirement that each variable occurs in 2 equations (to say at most $k$ equations), is there a similar nice combinatorial characterization of the satisfiability of the system of equations? This corresponds to a hypergraph version of the Tseitin formulas. It's easy to see that in this case if $\sum_{i=1}^{|b|} = 1\mod 2$ is odd then the system is unsatisfiable, but the other direction does not hold. Is there a nice sufficient condition for the satisfiability of such a system?

  • $\begingroup$ I don't think it is true that $\sum\limits_{i=1}^{|b|} b_i \equiv 1 (\mod 2)$ implies that the system is unsatisfiable. For example $\left\{\begin{array}{c} x + y = 1\\ x = 0 \\ \end{array}\right.$ The reason is that in Tseitin formula each variable appears in exactly two equations. The similar logic will be legit if we require each variable appear in exactly $k$ equations and $\sum\limits_{i=1}^{|b|} b_i \not\equiv 0 \mod k$. $\endgroup$ – Artur Riazanov Dec 5 '17 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.