Is the number of NP-complete problems finite?

Question

It should be straight forward to show that there are infinitely many NP-hard problems:

Proof: Take the problem Remove 1 Vertex 3-COL ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and yields a yes answer iff a vertex $x \in V$ exists which, when removed from $V$ yields a new graph $G'=(V\backslash\{x\}, \{(u,v) \in E\,|\, u \neq x \land v\neq x\}$ which is a positive instance of $3COL$.

$R1V3COL$ can indeed be reduced to 3-colorability problem (which is proven to be NP-complete) by (as an example reduction) simply removing a vertex from $G$ and testing if $G$ is 3-colorable. If $G$ is not 3-colorable remove another vertex from $G$ and test it. Repeat until there are no vertices left for testing.

Therefore we know $R1V3COL$ is an NP-hard problem.

We can now reduce $R2V3COL$ to a $R1V3COL$ problem (by a similar concept as shown above for $R1V3COL$ to $3COL$ to show that $R2V3COL$ is in NP-hard and so on for every Remove n Vertices 3-COL problem. In other words we can always reduce $R(n)V3COL$ to $R(n-1)V3COL$. Therefore we know that there have to be infinitely many NP-hard problems and we are done.

Now to my Lemma: I cannot think of a simple proof to show that a certain problem with infinitely many variations (like $R(n)V3COL$) is also in NP to prove NP-completeness and therefore prove that infinitely many problems are in the subclass NP-complete.

Answer 1

As in the comment, consider the collection of problems $N$-SAT (Is $\phi$, a logical formula in $N$-CNF, satisfiable?). Or $N$-coloring of graphs, for $N \ge 3$ (Can the graph be colored with $N$ colors?). Many NP-complete problems have some parameter (Is there a clique of size $k$ in the graph? Has the digraph a feedback vertex set of size $k$?).

Answer 2

Take any NP-complete problem, for instance $\text{SAT}$. Note that there are infinitely many unsatisfiable formulas. So let $\phi_1, \phi_2, \phi_3 \ldots$ be an infinite enumeration of (distinct) unsatisfiable formulas.

For each $i$, we can consider the problem $\text{SAT}_i = \text{SAT} \cup \{\phi_i\}$ i.e. the problem of deciding whether a given formula is either satisfiable, or equal to $\phi_i$.

This problem is clearly in NP and there is a straightforward reduction from $\text{SAT}$ to $\text{SAT}_i$: Given any formula $\phi$, we have $\phi \in \text{SAT}$ iff $(\phi \neq \phi_i) \land (\phi \in \text{SAT}_i)$.

Answer 3

For every integer k, take the travelling salesman problem with n > 1 cities where n is a power of k. (Picked the problem that way because all the instances are distinct, so we can say with good conscience that these are distinct problems).