# Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?

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?

• This problem (as, indeed, with any sparse problem) is not NP-hard unless PH collapses to the second level, by the Karp-Lipton theorem. Jul 27 '16 at 5:36
• This problem does not seem to be a "sparse" problem in the usual definition of sparse languages in complexity theory. Jul 27 '16 at 6:27
• 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. Jul 27 '16 at 16:09

Yes, and you'd be right. ​ ​ ​ 2^(2^(i+1)) = 2^((2^i)*(2^1)) = 2^((2^i)*2) = (2^(2^i))^2 , ​ so just
pad the input n-vertex instance of vertex cover with 2^(2^(ceil(log2(log2(n))))) isolated vertices.
For all positive integers c, a similar thing will apply when 2^(2^i) gets replaced with 2^(2^(c*i)).

However, under plausible assumptions, that's tight:

Let S be the set of functions from {0,1,2,3,...} to itself that are in ω(1), consider any functions
f and g in S, and let Q be the result of replacing 2^(2^i) with 2^(2^(f(i))) before applying
your sparse embedding. ​ If Q is NP-hard even under polynomial-time Turing reductions,
then ​ ​ ​ NP $\subset$ r.o.$\hspace{-0.04 in}\big(\hspace{-0.05 in}$DTIME(2^(n^(o(1))))/g$\hspace{-0.04 in}\big)$ , ​ where maxL(n) is an upper-bound
on the length of each of the reduction's oracle queries for n-bit inputs
and the advice can be any function h in S such that
max ​ ( ​ {0,1,2,3,...,maxL(n)-1,maxL(n)} ​ ∩ ​ Range(i $\mapsto$ 2^(2^(f(i)))) ​ ) ​ ​ ​ is r.o. at most n^(1/(h(n))).

Furthermore, if there is a function j in S such that ​ f(n)+j(n) ≤ f(n+1) ​ holds for all sufficiently large n, then the set of input-lengths on which the algorithm errs can be covered by a collection of
polynomial-length integer intervals such that the gaps between them have length n^(ω(1)),
and if additionally j is computable 2^(n^(o(1)))) time when n is the input itself, not the input's length,
then the advice can be removed. ​ (without losing the interval-cover property I just mentioned)