NP-complete language as a result of xoring two PTIME languages We define xor operation on languages $L,M\subseteq \{0,1\}^*$:
  $$L\oplus M = \{u\oplus v :|u|=|v|, u\in L, v\in M\}$$   $\oplus$ is
  defined as xor on postions, for example:  $001\oplus 100=101$   Show
  that there exist  languages $L,M\in PTIME$ such that $L\oplus M\in
 NP complete$


It is hard to me. I have been thinking a lot about it. My intuition is:

Write the problem as equations system and reduce 3-SAT to it. But, I am not sure if it is ok and, if yes, how to solve it.
This seems like a rather difficult question. Here is one approach.

Every 3CNF on $n$ variables can be encoded as a binary string of length $8n^3$ (how?). Consider the following two languages:
$$
\begin{align*}
L_1 &amp;= \bigcup_{n=1}^\infty \{ xy0^{8n^3} : |x|=n, |y|=8n^3, \text{$x$ is an assignment satisfying the 3CNF $y$} \}, \\
L_2 &amp;= \bigcup_{n=1}^\infty \{ x0^{8n^3}y : |x|=n, |y|=8n^3, \text{$x$ is an assignment satisfying the 3CNF $y$} \}.
\end{align*}
$$
These two languages are clearly in P, and so their XOR is clearly in NP. However,
$$
(L_1 \oplus L_2) \cap \bigcup_{n=1}^\infty \{0^ny^2 : |y|=8n^3\} = \bigcup_{n=1}^\infty \{0^n y^2 : |y|=8n^3, y \text{ is satisfiable}\},
$$
showing that $L_1 \oplus L_2$ is NP-complete.