# 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

Let $X$, $Y$ be non-trivial languages (ie either empty nor everything) such that the symmetric difference $(X \setminus Y) \cup (X \setminus Y)$ 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 (X \setminus Y)$ 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