# 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. Commented 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. Commented 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).
– user114966
Commented Jan 28, 2020 at 23:41

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

• Don't even need to take unsatisfable formulae $\phi_i$, any old infinite collection of formulae will do. Commented Nov 11, 2023 at 0:31

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

• Those are just instances of the travelling salesman problem of different sizes. Commented Jan 28, 2020 at 21:44
• So what? Each is its own problem. Commented Jan 29, 2020 at 7:32