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$
  • $\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$ – Ṃųỻịgǻňạcểơửṩ Jan 28 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$ – user5751924 Jan 28 at 18:51
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$?).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\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$ – Dmitry Jan 28 at 23:41
0
$\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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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