# Evaluating predicate on binary strings

Consider two unknown binary strings $$X = x_{1} x_{2} \dots x_{n^{2}}, \quad Y = y_{1} y_{2} \dots y_{n^{2}}, \quad x_{i}, y_{i} \in \{0, 1\} .$$ We may request a string $$Z = z_{1} z_{2} \dots z_{n^{2}}$$, where $$z_{i} = x_{i}$$ or $$z_{i} = y_{i}$$, no more than $$n + 1$$ times. So, for every request we set required $$z_{i}$$ (that is, $$x_{i}$$ or $$y_{i}$$) for every $$i$$.

Moreover, we have $$n$$ bits of unwritable memory, namely, every bit of that memory is set once and then does not change. This memory is avaliable all the time, but requested $$Z$$ strings drop out before the next request, so, we don't have complete list of all requested $$Z$$ strings.

The problem is to check if $$X = Y$$ with given $$n$$ bits and $$n + 1$$ times for $$Z$$ string request.

There is an extra question: is it possible to use $$\mathcal{O}(\log^{2}(n))$$ bits of memory and $$\mathcal{O}(\log(r))$$ requests.

I don't really understand area of CS that is closely related to the problem, could anyone give a hint?

• I can't understand the sentence beginning "We may request a string $Z$". Do you mean: "We may make up to $n+1$ queries, where each query consists of a string of $n^2$ letters, each of which is either 'X' or 'Y'; the response to a query consists of a string of $n^2$ bits, with the $i$-th bit in the response set to $x_i$ if the $i$-th letter in the query is 'X', and instead set to $y_i$ if the $i$-th letter in the query is 'Y'."? Nov 19 '19 at 1:30
• @j_random_hacker yes, every query is determined by string over $\{X, Y\}$, where each letter corresponds to unknown string from which the digit will be taken, and we may make up to $n + 1$ such queries. Nov 19 '19 at 1:37
• OK. That helps. Can you please edit the question accordingly, so people can understand what you are asking without having to read the comments? Thank you!
– D.W.
Nov 19 '19 at 6:15

You can think of $$X,Y$$ as $$n\times n$$ matrices with rows $$a_1,\ldots,a_n$$ and $$b_1,\ldots,b_n$$, respectively. Then $$X = Y$$ iff $$a_1 \oplus \cdots \oplus a_n = b_1 \oplus a_2 \oplus \cdots \oplus a_n = b_1 \oplus b_2 \oplus a_3 \oplus \cdots \oplus a_n = \cdots = b_1 \oplus \cdots \oplus b_n.$$