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