3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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'."? $\endgroup$ – j_random_hacker Nov 19 '19 at 1:30
  • $\begingroup$ @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. $\endgroup$ – matroid1998 Nov 19 '19 at 1:37
  • $\begingroup$ 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! $\endgroup$ – D.W. Nov 19 '19 at 6:15
0
$\begingroup$

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. $$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.