4
$\begingroup$

Suppose A∪B is NP-hard, does it follow that A is NP-hard or B is NP-hard?

Equivalently, is the property "not NP-hard" closed under union?

A related question was already asked:

Are NP-complete sets formed from two other sets only if at least one is NP-hard?

but it seems no consensus was formed.

$\endgroup$
2
$\begingroup$

If $P = NP$, then the only not-$NP$-hard sets are $\emptyset$ and $\Sigma^*$, and the statement trivially holds. So let us assume $P \neq NP$.

Then whenever $X$ is $NP$-hard, both $X$ and $X^C$ must contain an infinite c.e. set, namely "the image of the positive SAT-instances under the reduction" and "the image of the negative SAT-instances under the reduction". For if either of these sets were finite, we could get a P-algorithm for SAT.

By diagonalization, we can construct some set $X$ such that neither $X$ nor $X^C$ contain an infinite c.e.-set. Then $SAT \cap X$ and $SAT \cap X^C$ do not contain infinite c.e. sets, hence are both not $NP$-hard. But their union is SAT, and hence $NP$-hard.

To get a decidable counterexample, it should suffice to note that if $X$ is NP-hard, we not only have infinite c.e.~subsets of $X$ and $X^C$, but actually ones which can be computed in exponential time. Diagonalizing against those should doable in a decidable way; but I have not worked out the details.

$\endgroup$

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.