1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Jan 28, 2020 at 18:05
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jan 28, 2020 at 18:51

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
  • 4
    $\begingroup$ 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). $\endgroup$
    – user114966
    Commented Jan 28, 2020 at 23:41
3
$\begingroup$

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

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

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

$\endgroup$
2
  • 1
    $\begingroup$ Those are just instances of the travelling salesman problem of different sizes. $\endgroup$
    – vonbrand
    Commented Jan 28, 2020 at 21:44
  • 1
    $\begingroup$ So what? Each is its own problem. $\endgroup$
    – gnasher729
    Commented Jan 29, 2020 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.