3
$\begingroup$

Let's suppose I have an NP-complete problem A.

Can there be $A_1$, $A_2$ such that $A_1$ and $A_2$ are disjoint, $A = A_1 \cup A_2$, and $A_1$ and $A_2$ are NP-complete?

My guess would be yes. For example, just partition SAT into formulas with an even number of variables and formulas with an odd number.

Follow up: Can I partition $A$ into infinitely many such $A_i$? (I suppose yes: take formulas with $2^n$ variables, $3^n$, $5^n$, $7^n$, $11^n$, or something like that)

$\endgroup$
  • 2
    $\begingroup$ If you already know the answer, then why are you asking the question? Be more certain of yourself. $\endgroup$ – Yuval Filmus Mar 31 '14 at 4:49
  • 1
    $\begingroup$ Well, there remains the issue of showing that these subsets are actually NP-hard. Can you do this? $\endgroup$ – Raphael Mar 31 '14 at 8:19
1
$\begingroup$

There are many ways of accomplishing this. Consider SAT for example. Let SAT$_p$ denote a YES instance of SAT with $n$ clauses, where $p$ is the smallest prime factor of $n$. Clearly $\{ \mathrm{SAT}_p : p \text{ prime} \}$ is a partition of SAT. SAT$_p$ is clearly in NP. To show that it is NP-hard, we reduce from SAT. Given an instance of SAT having $n$ clauses, with add $m$ times the clause $x \lor y \lor z$ ($m$ to be chosen later so that $p$ is the smallest prime factor of $n+m$), where $x,y,z$ are new variables. The new instance is satisfiable iff the original one is, and by definition $p$ is the smallest prime factor of $n$. It remains to define $m$ and show that the reduction can be done in polynomial time (this depends only on the value of $m$ compared to the value of $n$).

Let $P$ be the product of all primes at most $p$. We will choose $m$ so that $n + m \equiv p \pmod{P}$. Clearly some $p < P$ fits the bill. I leave the reader to show that $p$ is the smallest prime factor of $n + m$.

$\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.