Let there be a language $A$ which is NP complete and language $B$ which is a finite language, is the union of $A \cup B$ NP complete language?

  • 1
    $\begingroup$ As a general thumb rule, adding and/or removing a finite number of words from a language in any "well-known" class, creates a new language in the same class. (Of course, this is not true for all classes of problems, e.g. a class containing only one problem. However, if a class is so "fragile" to be affected by finite modifications, then the class is not very interesting and hardly becomes a "well-known" one) $\endgroup$ – chi Jun 22 '18 at 15:11

The answer is yes, and this is a special case of the following statement:

Let $X$, $Y$ be non-trivial languages (ie either empty nor everything) such that the symmetric difference $(X \setminus Y) \cup (Y \setminus X)$ is finite. Then $X \leq Y$ (linear time, constant space manyone reduction).

The reduction just tests whether the input is any of the finitely many values in $(X \setminus Y) \cup (Y \setminus X)$ and proceeds in a hard-coded way there. This takes constant time+space. Otherwise, it copies the input, since $X$ and $Y$ will agree there.

How to use this: For NP-hardness of $A \cup B$, set $X := A$ and $Y := A \cup B$. For NP-membership of $A \cup B$, set $X := A \cup B$ and $Y := A$. Note that the symmetric difference of $A$ and $A \cup B$ is included in $B$, hence if $B$ is finite, so is the symmetric difference.

  • $\begingroup$ I think the symmetric difference of the two language doesn't have to be finite (since one language is NPC doesn't have to be finite) Let's say one language is vertex-cover and the other language is $B = \{a\}$ then the symmetric difference is $A \cup B$ which is not finite $\endgroup$ – user1247066 Jun 21 '18 at 11:36
  • $\begingroup$ If $B$ is finite, then the symmetric difference of $A$ and $A \cup B$ is finite (since it is a subset of $B$). $\endgroup$ – Arno Jun 21 '18 at 12:25
  • $\begingroup$ I think what is confusing in this answer is the naming of the languages w.r.t. the question. OP's NP-complete $A$ is also named $A$ in this answer, but Arno's $B$ is actually $A \cup B$ from the question, not the sole finite $B$! Also one may add a short argument why $A \cup B$ actually is in NP. $\endgroup$ – ttnick Jun 22 '18 at 9:28
  • 1
    $\begingroup$ @PHPNick Point taken. I've renamed stuff. $\endgroup$ – Arno Jun 22 '18 at 9:57
  • $\begingroup$ A bit old question, but isn't the symmetric difference is $\left(X\backslash Y\right)\cup\left(Y\backslash X\right)$? Also does it mean that $X\leq Y$ and $Y\leq X$? Is it also polynominal? $\endgroup$ – vesii Jul 17 at 19:17

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.