# Partitioning NP-complete problems

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)

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

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