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?
3
-
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 GrochowJul 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 DeyJul 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$– Joshua GrochowJul 27, 2016 at 16:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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)