[Solved]: About the notation of XOR-SAT

Problem Detail: 

I am a bit confused by the notation here, http://www.boazbarak.org/sos/files/lec3.pdf

• Given 3 Boolean variables $x_i, x_j, x_k$ what is supposed to be the meaning of $x_i \oplus x_j \oplus x_k$?

  Is this to be understood as say $((x_i \oplus x_j )\oplus x_k )$? And hence this is true for only $2$ cases $x_i =0, x_j = 1, x_k =0$ and $x_i = 1, x_j = 0, x_k = 0$ ?

  But then we could have bracketed it as $(x_i \oplus (x_j \oplus x_k))$ and then the only true assignments would have looked as $x_i = 0, x_j =1, x_k = 0$ and $x_i = 0, x_j =0, x_k = 1$ and these are different.

  Also one could have used commutativity to write it in other re-arranged forms and gotten different true selections!

• But then the note above seems to claim that if the $x_a$s are coming as coordinates of a vector $x \in \{\pm 1\}^n$ then the product $x_ix_j x_k$ is the same as having a linear equation in those $3$ variables. Why so? (for example an assignment $x_i = x_j = x_k =1$ will evaluate to $1$ for the product but under mod 2 arithmetic $x_i + x_j + x_k = 0$ for this assignment!)

Also it is being claimed that the value of $x_ix_jx_k$ can only be $\pm 1$ (which they denote as $a_{ijk}$) for $x \in \{\pm 1\}^n$ and that is okay only if one ignores the first claim that these are supposed to be linear equations!

---

This $x_ix_j x_k$ product notation looks more confusing later on when they say that corresponding to two subsets $S, T \subset \{1,..,n\}$ one can take two expressions of the form $x_S = \prod_{i \in S} x_i$ and $x_T = \prod_{i \in T} x_i$ and construct $x_U = x_S x_T$ and that this somehow corresponds to doing ``$U = S \oplus T$" - and I don't know what it means to take a XOR of two subsets!

Asked By : gradstudent

Answered By : Yuval Filmus

XOR is an associative operation, so $x_i \oplus x_j \oplus x_k$ is unambiguous. There are in fact four satisfying assignments, given by $$ (x_i,x_j,x_k) \in \{(0,0,1),(0,1,0),(1,0,0),(1,1,1)\}. $$

XOR satisfies the useful property $$ (-1)^{x \oplus y} = (-1)^x (-1)^y. $$ Therefore $x_i \oplus x_j \oplus x_k = 1$ is the same as $$ (-1)^{x_i} (-1)^{x_j} (-1)^{x_k} = (-1)^1.$$ If we think of our variables as $X_i = (-1)^{x_i}$, then the equation $x_i \oplus x_j \oplus x_k = 1$ is completely equivalent to $X_i X_j X_k = -1$. Since XOR is really just addition in the group $\mathbb{Z}_2$, you can think of both formulations as linear equations.

---

Yet another interpretation of XOR is in terms of sets. Just as AND corresponds to intersection and OR to union, the XOR operation corresponds to symmetric difference, sometimes denoted $\triangle$ or $\Delta$. You can easily check that $x_S x_T = x_{S \triangle T}$, essentially using $x_i^2 = 1$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54424

3.2K people like this

 Download Related Notes/Documents