Partitioning NP-complete problems
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 &lt; P$ fits the bill. I leave the reader to show that $p$ is the smallest prime factor of $n + m$.