1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What NP-complete languages do I know? SAT, 3SAT, HAMPATH, TSP, Vertex Cover, k Clique... Non of which I know what A⊕A is!! $\endgroup$ – Anwar Saiah Mar 2 '18 at 13:20
  • 1
    $\begingroup$ @AnwarSaiah It seems your real question is understanding what $A\oplus A$ is. $\endgroup$ – Hendrik Jan Mar 2 '18 at 16:00
  • $\begingroup$ 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. $\endgroup$ – Anwar Saiah Mar 2 '18 at 18:39
  • $\begingroup$ It seems to me that L is always in NP, so if P=NP it is always NP-complete. $\endgroup$ – Willard Zhan Mar 2 '18 at 19:29
  • $\begingroup$ @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). $\endgroup$ – Tom van der Zanden Mar 3 '18 at 9:40
3
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Anwar Saiah Mar 10 '18 at 19:58
  • $\begingroup$ $A\bigoplus B$ is defined differently in the question. $\endgroup$ – Tom van der Zanden Mar 10 '18 at 20:01
  • $\begingroup$ You are right guys, my bad. $\endgroup$ – Kyrylo Yefimenko Mar 10 '18 at 20:25
  • $\begingroup$ Sorry for the ambiguity, I fixed the question's definition. I think I'm now clear on the XOR operation. $\endgroup$ – Anwar Saiah Mar 10 '18 at 20:29

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.