# XOR of two NP-Complete languages

Given two NP-Complete languages A and B, show that the language:

$L = A\bigoplus B =\{a\bigoplus b \mid a \in A, b \in B, |a|=|b|\}$

is not necessarily NP-Complete.

Remember $a\bigoplus b$ when $|a|=|b|$ gives 0 when they have the same digit and 1 otherwise.

Example: 0110$\bigoplus$ 0101 = 0011

I have tried to solve this in my exam only was not so accurate..Help needed.

• What NP-complete languages do I know? SAT, 3SAT, HAMPATH, TSP, Vertex Cover, k Clique... Non of which I know what A⊕A is!! – Anwar Saiah Mar 2 '18 at 13:20
• @AnwarSaiah It seems your real question is understanding what $A\oplus A$ is. – Hendrik Jan Mar 2 '18 at 16:00
• From my understanding, A⊕A will give zeros when the word is XORed with it's self. So we will be having a lot of words all zeros. I'm not sure why that would help. Unless I find a language that has only one word of each length, so words that are 3 chars long are only one word. – Anwar Saiah Mar 2 '18 at 18:39
• It seems to me that L is always in NP, so if P=NP it is always NP-complete. – Willard Zhan Mar 2 '18 at 19:29
• @WillardZhan Even if P=NP there are languages in NP that are not NP-complete. That is actually a nice trick to solve this exercise (my earlier hint pointed in the wrong direction). – Tom van der Zanden Mar 3 '18 at 9:40

$A\bigoplus B$ can be empty (and thus definitely not $NP$-complete) if we pick $A$ and $B$ carefully. For instance, if all strings in $A$ have even length and all strings in $B$ have odd length then $A\bigoplus B$ is empty.

It is fairly easy to modify any $NP$-complete language $L$ to have either only even (resp., odd) strings: let $L'$ be the language consisting of strings formed by prepending $1$ to any odd (resp., even) length string from $L$ and prepending $01$ to any even (resp., odd) length string from $L$.

Note that we can easily recover the original language $L$ from $L'$ by noting that any string that was originally of odd length starts with a $1$ (and thus we must drop the first character), and any string that was originally of even length starts with $01$ (and thus we must drop the first two characters).

First, notice that $A \oplus B = A \space \Delta \space B = \big( A \space \backslash \space B \big) \cup \big(B \space \backslash \space A \big)$.

To prove that it is not always the case that$\space A \space \oplus \space B \in NP-COMPLETE \space$ you only need to provide one example that falsifies the statement.

Take $A = B = SAT \in NP-COMPLETE$. Then $A \oplus B = \emptyset \notin NP-COMPLETE.$

• Take u,v $\epsilon A$ where as they are different words with the same length, their xor is not empty. What I want to say is that $A \bigoplus B$ is not empty! – Anwar Saiah Mar 10 '18 at 19:58
• $A\bigoplus B$ is defined differently in the question. – Tom van der Zanden Mar 10 '18 at 20:01
• You are right guys, my bad. – Kyrylo Yefimenko Mar 10 '18 at 20:25
• Sorry for the ambiguity, I fixed the question's definition. I think I'm now clear on the XOR operation. – Anwar Saiah Mar 10 '18 at 20:29