World's most popular travel blog for travel bloggers.

[Solved]: About the notation of XOR-SAT

, , No Comments
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

0 comments:

Post a Comment

Let us know your responses and feedback