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?

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

1 Answer 1


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)


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.