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

• You don't need to reduce the 3SAT to $L\oplus M$ in order to prove $L\oplus M \in NP$. It is enough to show that $x\in L\oplus M$ is verifiable in polynomial time on a deterministic TM. However, the reduction of 3SAT to $L\oplus M$ would also imply $L\oplus M \in NP$, but the latter may be harder to demonstrate. – fade2black Aug 10 '17 at 23:02
• I edited my post – Carol Aug 10 '17 at 23:11
• Now, try to solve it yourself. First show that if both $L$ and $M$ in $PTIME$ then $L\oplus M$ is in $NP$. This part is easy - you don't need to come up with a concrete $L$ and $M$. Then try to come up with concrete $L$ and $M$ such that an $NP$-complete (maybe 3SAT) problem is reduced to $L\oplus M$. That part is harder. If you get stuck you can post what you have done and where you have got stuck. – fade2black Aug 10 '17 at 23:17

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 &= \bigcup_{n=1}^\infty \{ xy0^{8n^3} : |x|=n, |y|=8n^3, \text{x is an assignment satisfying the 3CNF y} \}, \\ L_2 &= \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.

• Why $L_1$ is in PTIME ? After all, in this way I can solve $\phi$ in 3CNF in P: $L_1= \{x : \text{$x$is an assigment satisfying given$\phi$3CNF formula} \}$ – Haskell Fun Aug 11 '17 at 12:21
• Your example is a finite language and so in $\mathsf{P}$. In fact, it has a constant time algorithm. The algorithm reads the first $n$ bits on the tape, and then can immediately answer Yes or No. – Yuval Filmus Aug 11 '17 at 12:37
• I understand that my approach (below) is not ok, because finite languages are regular. However, your $L_1$ is thing that I don't understand it. I can't see how you can do it in PTIME. – Haskell Fun Aug 11 '17 at 17:47
• You can check whether a truth assignment satisfies a formula in polynomial time. – Yuval Filmus Aug 11 '17 at 19:02
• Could this be simplified conceptually by choosing $L_1 = \bigcup \{xy :|x|=n,|y|=8n^3, x \text{ is an assignment satisfying the 3CNF } y\}$ and $L_2= \bigcup \{x0^{8n^3}:|x|=n \}$. In that way $L_2$ just hides the assignment . – Hendrik Jan Aug 23 '17 at 15:24

I have other idea, I am not sure if it is correct:
Let $k$ will be number of clauses and $n=5$ number of variables. I reduce $3-$SAT problem, for each clause $c_i=(x_1, x_3, \neg x_5)$ I create language $$L_i= \{1\{0,1\}\{0,1\}\{0,1\}\{0,1\},\{0,1\}\{0,1\}1\{0,1\}\{0,1\}, \{0,1\}\{0,1\}\{0,1\}\{0,1\}0 \}$$
So $L_i$ contains patterns which satisfy $c_i$. Of course $L_i\in P$.
Let $$L=L_1\cdot ...\cdot L_k$$, $$M=\{(\{0,1\}^n)^k\}$$
Hence, $M$ contains all possible assigments reapeted $k$ times. Now, we can check if $0^{kn}$ belongs to $L\oplus M$ in order to check if given $3CNF$ formula is satisfable. The meaning is that $0^{kn}\in M$ does mean that each clause agree with some assigment (agreeing corresponds to satisfability)

• The language $L \oplus M$ is finite, and so trivially in $\mathsf{P}$. – Yuval Filmus Aug 11 '17 at 11:17
• @YuvalFilmus in 3SAT problem there are also finite numbers of assigments, however 3SAT is in NP. Where is the key ? – Haskell Fun Aug 11 '17 at 11:56
• Your language $L \oplus M$ is finite. The language of satisfiable 3CNF is infinite. The key is that $L,M$ in your case depend on a formula. What you want is a single pair $L,M$ that would work for all formulas. – Yuval Filmus Aug 11 '17 at 12:36
• yes, but @HaskellFun has to take a formula $F$ and convert it to that problem. Why is it not ok? – Carol Aug 11 '17 at 13:30
• @Carol The construction just doesn't work. – Yuval Filmus Aug 11 '17 at 19:13