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$ – Joshua Grochow Jul 27 '16 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 '16 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$ – Joshua Grochow Jul 27 '16 at 16:09
  • $\begingroup$ Stupid follow-up question: doesn't replacing 2^2^n with Tetrate(2,2n) give a trivially NPI problem? It's in NP, but black box access to it is unhelpful wrt polytime reductions because (for appropriate input sizes) the only interesting instances you can reduce to are of size O(log n), where you can just brute force the solution in poly(n) time rather than use the black-box. Or am I misunderstanding something? $\endgroup$ – Yonatan N Jul 28 '16 at 1:35

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, privacy policy and cookie policy

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