patternMinor
Is the union of NP Complete language and a finite language (in P) NP Complete?
Viewed 0 times
thefiniteunionlanguagecompleteand
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#93301, answer score: 2
Revisions (0)
No revisions yet.