<p>Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say that the problem P is NP-hard?</p>

CC BY-SA 3.0
2016-07-27T05:36:47.587Z
This problem (as, indeed, with any sparse problem) is not NP-hard unless PH collapses to the second level, by the Karp-Lipton theorem.
Joshua Grochow
CC BY-SA 3.0
2016-07-27T06:27:10.300Z
This problem does not seem to be a "sparse" problem in the usual definition of sparse languages in complexity theory.
Palash Dey
CC BY-SA 3.0
2016-07-27T16:09:18.337Z
Ah, of course (that's what I get for writing late at night): the set of *lengths* where your problem has yes-instances is very sparse, but at each of those lengths $n=2^{2^i}$ it will have the usual exponentially many yes- and no-instances.
Joshua Grochow
<cc.complexity-theory><ds.algorithms><np-hardness><np><np-complete>
Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?
Palash Dey
# Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?

(Asked by: username_0 on 2016-07-27)

Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say that the problem P is NP-hard?

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness, np, np-complete

> **Comments:**
> **username_1**: This problem (as, indeed, with any sparse problem) is not NP-hard unless PH collapses to the second level, by the Karp-Lipton theorem.  
> **username_0**: This problem does not seem to be a "sparse" problem in the usual definition of sparse languages in complexity theory.  
> **username_1**: Ah, of course (that's what I get for writing late at night): the set of *lengths* where your problem has yes-instances is very sparse, but at each of those lengths $n=2^{2^i}$ it will have the usual exponentially many yes- and no-instances.  

---

## 0 answers

