# Is the number of NP-complete problems finite?

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.

• There seems to have an infinite number of NP-complete problems though most have no practical significance. We could create an arbitrary NP-complete algorithm in terms of any other NP-complete algorithms arranged in an appropriate way. Jan 28, 2020 at 18:05
• You can get a more straightforward proof with the series of n-sat problems for instance. Generally, any problem which stays np-complete with a varying integer parameter will do. Jan 28, 2020 at 18:51

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$$?).
• Is there a clique of size k in the graph? You want to fix k? Then it won't be a NP-complete problem (since you can do this in $O(n^k)$ time).