# Is the union of NP Complete language and a finite language (in P) NP Complete?

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?

• 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) – 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.

• 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 – user1247066 Jun 21 '18 at 11:36
• If $B$ is finite, then the symmetric difference of $A$ and $A \cup B$ is finite (since it is a subset of $B$). – Arno Jun 21 '18 at 12:25
• 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. – ttnick Jun 22 '18 at 9:28
• @PHPNick Point taken. I've renamed stuff. – Arno Jun 22 '18 at 9:57
• 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? – vesii Jul 17 at 19:17