<p><strong>Question 1:</strong> For a function $f(n)$ lets say that $f$ is <em>sub-polynomial</em> if $\forall \epsilon &gt; 0, f(n) = O(n^\epsilon)$. The Exponential Time Hypothesis (ETH) states that 3-SAT needs $2^{\epsilon n}$ time for some $\epsilon &gt; 0$. Let's postulate a much weaker version, ``<em>Weak Exponential Time Hypothesis</em>'' (WETH): There exists an $\epsilon &gt; 0$ such that $3$-SAT requires $2^{\epsilon n^\epsilon}$ time. </p>

<p><strong>Claim:</strong> <em>If $f$-bounded Independent Set is NP-hard for any sub-polynomial function $f$ then the WETH fails</em>.</p>

<p><strong>Proof:</strong> Supose $f$-bounded Independent Set is NP-hard under Turing-reductions for some any sub-polynomial function $f$. Then there exists a constant $c$ and an $O(n^c)$ time algorithm for $3$-SAT with $n$-variables that makes at most $O(n^c)$ oracle calls to $f$-bounded Independent Set with at most $O(n^c)$ vertices. </p>

<p>From this algorithm we make an algorithm for $3$-SAT where the oracle calls to $f$-bounded Independent Set are replaced by the $O(|V(G)|^{k+2})$ time brute force algorithm. The running time of this algorithm is upper bounded by
$O((n^c) \cdot (n^c)^{f(n^c)+2}) = 2^{O(\log n \cdot f(n^c))}$. For any $\epsilon &gt; 0$, pick $\delta = \epsilon / 2c$. Since $f$ is sub-polynomial we have that $f(n^c) = O((n^c)^\delta) = O(n^{\epsilon / 2})$. Therefore the running time of the algorithm is upper bounded by $2^{O(\log n \cdot n^{\epsilon / 2})} = 2^{O(n^{\epsilon})}$, contradicting the WETH.</p>

<hr>

<p><strong>Question 2:</strong> Let's say that $f$ <em>computably tends to infinity</em> if there exists a computable function $g : \mathbb{N} \rightarrow \mathbb{N}$ such that for every $c$ and every $n \geq g(c)$, $f(n) \geq c$.</p>

<p><strong>Claim:</strong> <em>If $f$-bounded Independent Set is in P for any function $f$ that computably tends to infinity, then FPT = W[1]</em>.</p>

<p><strong>Proof:</strong> Assuming the existence of a polynomial time algorithm for $f$-bounded Independent Set we will give an FPT algorithm for Independent Set, proving FPT=W[1]. </p>

<p>Given as input $G$ and $k$, set $n = |V(G)|$ and compute $g(k)$. Note that computing $g(k)$ takes time that is only a function of $k$. If $g(k) \leq n$ run the polynomial time algorithm for $f$-bounded Independent Set, this will output the correct answer because $k \leq f(n)$. If $g(k) &gt; n$ then run the brute force $n^{k+2}$ algorithm, this takes time $g(k)^{k+2}$. In total the running time is bounded by $O(n^c + h(k))$ for some constant $c$ independent of $k$ and some function $h$.</p>

<hr>

<p><strong>Remark:</strong> Note that nothing here is specific to Independent Set. The first argument works for any problem with a $O(n^{k^c})$ time algorithm for some $c$, while the second argument works for any decidable problem.</p>

CC BY-SA 3.0
2017-05-25T15:31:48.967Z
Nice exposition, thanks!  Is there a name in the FPT community for the subclass of XP where the running time is $|x|^{\text{poly}(k)}$ as you suggest for the first argument, as a kind of polynomial version of XP?
András Salamon
CC BY-SA 3.0
2017-05-25T16:51:57.567Z
I don't remember this class having any name, but it's pretty natural so it might well be hidden away somewhere.
daniello
CC BY-SA 3.0
2017-05-25T18:39:44.863Z
Have asked a new question https://cstheory.stackexchange.com/q/38299 about the name for this class.
András Salamon
CC BY-SA 3.0
2017-05-25T20:35:14.953Z
The running time of an algorithm A that decides a problem P is always computable -- run A on all inputs of size $n$, count the number of steps, and output the maximum. For the same reason the running time of the algorithm that computes $g( k)$ is computable.
daniello
CC BY-SA 3.0
2017-05-25T12:16:59.443Z
2017-05-25T12:16:59.443Z
daniello
<p>Independent Set (IS) is the $\mathsf{NP}$-complete decision problem</p>

<p><em>Input:</em> graph $G$ with $v=|V(G)|$, integer $k$<br>
<em>Question:</em> is there an independent set $S \subseteq V(G)$ with at least $k$ vertices?</p>

<p>Similarly, we can define $f(v)$-bounded IS as the promise version of IS, where the promise is that $k \le f(v)$.
Note that the function parameter depends only on the number of vertices in the input graph.</p>

<p>It is straightforward to show that when $f(v) = v/c$ for some constant $c$, then $f(v)$-bounded IS remains $\mathsf{NP}$-hard.
This is because IS can be reduced to $f(v)$-bounded IS by blowing up the number of vertices by at most a factor of $c$.
Similarly, when $f(v)=v^{1/c}$ for some constant $c$, then $f(v)$-bounded IS is also still $\mathsf{NP}$-hard, by blowing up the number of vertices by a power of $c$.</p>

<p>On the other hand, when $k$ is a constant, then $k$-bounded IS can be decided in polynomial time by exhaustively checking each of the $\binom{v}{k} = \Theta(v^k)$ different $k$-subsets, in at most $O(v^{k+2})$ steps.</p>

<p>This suggests that there is a spectrum of hardness defined via functions restricting the largest independent set that is sought in any instance.
This is, in fact, the case: <a href="http://dx.doi.org/10.1007/978-3-540-70583-3_16" rel="noreferrer">Bodirsky and Grohe 2008</a> (<a href="http://www.lix.polytechnique.fr/~bodirsky/publications/nodich.pdf" rel="noreferrer">preprint</a>) and <a href="http://dx.doi.org/10.1007/978-3-540-70575-8_48" rel="noreferrer">Chen, Thurley, Weyer 2008</a> (<a href="http://basics.sjtu.edu.cn/~chen/papers/icalp.pdf" rel="noreferrer">preprint</a>) established such results non-constructively via versions of Ladner's theorem, conditional on $\mathsf{P} \ne \mathsf{NP}$.</p>

<p>Keeping in mind that asymptotic behaviour does not induce a total order on functions,</p>

<blockquote>
  <p>what is a "smallest" function $f(v)$ such that $f(v)$-bounded IS is $\mathsf{NP}$-hard?</p>
</blockquote>

<p>In particular, is there some function $f(v)=o(v^{1/c})$ for every constant $c&gt;0$ for which bounded IS is hard?
(I'd be happy with an argument that is conditional on a common hypothesis such as ETH or $W[1] \ne \mathsf{FPT}$.)</p>

<p>Note that while $f(v) = v^{1/\lg v} = 2$ yields a polynomial upper bound on time, the somewhat faster growing function $f(v)=v^{1/\lg\lg v}$ yields a bound for exhaustive search that is superpolynomial but subexponential.
It would therefore also be interesting to establish whether there is a function $f(v) = \omega(1)$ such that $f(v)$-bounded IS is still in $\mathsf{P}$.</p>

CC BY-SA 3.0
2017-05-23T21:17:59.853Z
I think if $f(v)$ bounded IS is NP-hard for $f(v) = v^{o(1)}$ then the ETH fails
daniello
CC BY-SA 3.0
2017-05-23T23:14:59.347Z
@daniello, I wasn't able to prove that $\sqrt{v}$-bounded IS is not NP-hard unless the ETH fails, although this was the original aim that led to this question.  A slightly padded NP-hard problem may have a subexponential algorithm even in terms of its natural parameters, purely because of its inefficient representation.  If my statement about NP-hardness of $\sqrt{v}$-bounded IS is right, then perhaps the structure of 3SAT can't be embedded inside $f(v)$-bounded IS without some kind of deformation in the reduction, that acts like padding?
András Salamon
CC BY-SA 3.0
2017-05-24T07:25:46.050Z
Closely related questions are discussed in Christos H. Papadimitriou, Mihalis Yannakakis: On Limited Nondeterminism and the Complexity of the V-C Dimension. J. Comput. Syst. Sci. 53(2): 161-170 (1996)
Gamow
CC BY-SA 3.0
2017-05-24T15:51:03.610Z
@AndrasSalamon what I mean is that if the NP-hardness reduction takes $n$-variable $3$-SAT instances to $f(v)$ bounded instances of size $n^c$ then brute forcing the output instances will take time $(n^c)^{f(n^c)}$. If $f(n) = n^{1/g(n)}$ with $g(n)$ tending to infinity with $n$ then 3-SAT gets solved in time $(n)^{c \cdot n^{c/g(n)}}$ which for sufficiently large $n$ is $O(n^{n^{1/2}})$ which is subexponential.
daniello
CC BY-SA 3.0
2017-05-24T22:30:41.833Z
@daniello so the bound $v^{1/c}$ yields an NP-hard problem, but $v^{o(1)}$ cannot (unless the ETH fails).  I'm not sure this is enough to conclude there is no function that is $o(v^c)$ for all $c>0$, but seems close enough for an answer.
András Salamon
<cc.complexity-theory><np-hardness><conditional-results>
Limits of variants of Independent Set?
András Salamon
# Limits of variants of Independent Set?

(Asked by: username_0 on 2017-05-23)

Independent Set (IS) is the $\mathsf{NP}$-complete decision problem

*Input:* graph $G$ with $v=|V(G)|$, integer $k$  
*Question:* is there an independent set $S \subseteq V(G)$ with at least $k$ vertices?

Similarly, we can define $f(v)$-bounded IS as the promise version of IS, where the promise is that $k \le f(v)$.
Note that the function parameter depends only on the number of vertices in the input graph.

It is straightforward to show that when $f(v) = v/c$ for some constant $c$, then $f(v)$-bounded IS remains $\mathsf{NP}$-hard.
This is because IS can be reduced to $f(v)$-bounded IS by blowing up the number of vertices by at most a factor of $c$.
Similarly, when $f(v)=v^{1/c}$ for some constant $c$, then $f(v)$-bounded IS is also still $\mathsf{NP}$-hard, by blowing up the number of vertices by a power of $c$.

On the other hand, when $k$ is a constant, then $k$-bounded IS can be decided in polynomial time by exhaustively checking each of the $\binom{v}{k} = \Theta(v^k)$ different $k$-subsets, in at most $O(v^{k+2})$ steps.

This suggests that there is a spectrum of hardness defined via functions restricting the largest independent set that is sought in any instance.
This is, in fact, the case: [Bodirsky and Grohe 2008](http://dx.doi.org/10.1007/978-3-540-70583-3_16) ([preprint](http://www.lix.polytechnique.fr/~bodirsky/publications/nodich.pdf)) and [Chen, Thurley, Weyer 2008](http://dx.doi.org/10.1007/978-3-540-70575-8_48) ([preprint](http://basics.sjtu.edu.cn/~chen/papers/icalp.pdf)) established such results non-constructively via versions of Ladner's theorem, conditional on $\mathsf{P} \ne \mathsf{NP}$.

Keeping in mind that asymptotic behaviour does not induce a total order on functions,

> what is a "smallest" function $f(v)$ such that $f(v)$-bounded IS is $\mathsf{NP}$-hard?

In particular, is there some function $f(v)=o(v^{1/c})$ for every constant $c>0$ for which bounded IS is hard?
(I'd be happy with an argument that is conditional on a common hypothesis such as ETH or $W[1] \ne \mathsf{FPT}$.)

Note that while $f(v) = v^{1/\lg v} = 2$ yields a polynomial upper bound on time, the somewhat faster growing function $f(v)=v^{1/\lg\lg v}$ yields a bound for exhaustive search that is superpolynomial but subexponential.
It would therefore also be interesting to establish whether there is a function $f(v) = \omega(1)$ such that $f(v)$-bounded IS is still in $\mathsf{P}$.

**Tags:** cc.complexity-theory, np-hardness, conditional-results
> **Comments:**
> **username_1**: I think if $f(v)$ bounded IS is NP-hard for $f(v) = v^{o(1)}$ then the ETH fails  
> **username_0**: @daniello, I wasn't able to prove that $\sqrt{v}$-bounded IS is not NP-hard unless the ETH fails, although this was the original aim that led to this question.  A slightly padded NP-hard problem may have a subexponential algorithm even in terms of its natural parameters, purely because of its inefficient representation.  If my statement about NP-hardness of $\sqrt{v}$-bounded IS is right, then perhaps the structure of 3SAT can't be embedded inside $f(v)$-bounded IS without some kind of deformation in the reduction, that acts like padding?  
> **username_2**: Closely related questions are discussed in Christos H. Papadimitriou, Mihalis Yannakakis: On Limited Nondeterminism and the Complexity of the V-C Dimension. J. Comput. Syst. Sci. 53(2): 161-170 (1996)  
> **username_1**: @AndrasSalamon what I mean is that if the NP-hardness reduction takes $n$-variable $3$-SAT instances to $f(v)$ bounded instances of size $n^c$ then brute forcing the output instances will take time $(n^c)^{f(n^c)}$. If $f(n) = n^{1/g(n)}$ with $g(n)$ tending to infinity with $n$ then 3-SAT gets solved in time $(n)^{c \cdot n^{c/g(n)}}$ which for sufficiently large $n$ is $O(n^{n^{1/2}})$ which is subexponential.  
> **username_0**: @daniello so the bound $v^{1/c}$ yields an NP-hard problem, but $v^{o(1)}$ cannot (unless the ETH fails).  I'm not sure this is enough to conclude there is no function that is $o(v^c)$ for all $c>0$, but seems close enough for an answer.  

---

## 1 answers

### Answer by username_1 on 2017-05-25. Score: 3 | Accepted answer

**Question 1:** For a function $f(n)$ lets say that $f$ is *sub-polynomial* if $\forall \epsilon > 0, f(n) = O(n^\epsilon)$. The Exponential Time Hypothesis (ETH) states that 3-SAT needs $2^{\epsilon n}$ time for some $\epsilon > 0$. Let's postulate a much weaker version, ``*Weak Exponential Time Hypothesis*'' (WETH): There exists an $\epsilon > 0$ such that $3$-SAT requires $2^{\epsilon n^\epsilon}$ time.

**Claim:** *If $f$-bounded Independent Set is NP-hard for any sub-polynomial function $f$ then the WETH fails*.

**Proof:** Supose $f$-bounded Independent Set is NP-hard under Turing-reductions for some any sub-polynomial function $f$. Then there exists a constant $c$ and an $O(n^c)$ time algorithm for $3$-SAT with $n$-variables that makes at most $O(n^c)$ oracle calls to $f$-bounded Independent Set with at most $O(n^c)$ vertices.

From this algorithm we make an algorithm for $3$-SAT where the oracle calls to $f$-bounded Independent Set are replaced by the $O(|V(G)|^{k+2})$ time brute force algorithm. The running time of this algorithm is upper bounded by
$O((n^c) \cdot (n^c)^{f(n^c)+2}) = 2^{O(\log n \cdot f(n^c))}$. For any $\epsilon > 0$, pick $\delta = \epsilon / 2c$. Since $f$ is sub-polynomial we have that $f(n^c) = O((n^c)^\delta) = O(n^{\epsilon / 2})$. Therefore the running time of the algorithm is upper bounded by $2^{O(\log n \cdot n^{\epsilon / 2})} = 2^{O(n^{\epsilon})}$, contradicting the WETH.

---

**Question 2:** Let's say that $f$ *computably tends to infinity* if there exists a computable function $g : \mathbb{N} \rightarrow \mathbb{N}$ such that for every $c$ and every $n \geq g(c)$, $f(n) \geq c$.

**Claim:** *If $f$-bounded Independent Set is in P for any function $f$ that computably tends to infinity, then FPT = W[1]*.

**Proof:** Assuming the existence of a polynomial time algorithm for $f$-bounded Independent Set we will give an FPT algorithm for Independent Set, proving FPT=W[1].

Given as input $G$ and $k$, set $n = |V(G)|$ and compute $g(k)$. Note that computing $g(k)$ takes time that is only a function of $k$. If $g(k) \leq n$ run the polynomial time algorithm for $f$-bounded Independent Set, this will output the correct answer because $k \leq f(n)$. If $g(k) > n$ then run the brute force $n^{k+2}$ algorithm, this takes time $g(k)^{k+2}$. In total the running time is bounded by $O(n^c + h(k))$ for some constant $c$ independent of $k$ and some function $h$.

---

**Remark:** Note that nothing here is specific to Independent Set. The first argument works for any problem with a $O(n^{k^c})$ time algorithm for some $c$, while the second argument works for any decidable problem.

> **Comments:**
> **username_0**: Nice exposition, thanks!  Is there a name in the FPT community for the subclass of XP where the running time is $|x|^{\text{poly}(k)}$ as you suggest for the first argument, as a kind of polynomial version of XP?  
> **username_1**: I don't remember this class having any name, but it's pretty natural so it might well be hidden away somewhere.  
> **username_0**: Have asked a new question https://cstheory.stackexchange.com/q/38299 about the name for this class.  
> **username_1**: The running time of an algorithm A that decides a problem P is always computable -- run A on all inputs of size $n$, count the number of steps, and output the maximum. For the same reason the running time of the algorithm that computes $g( k)$ is computable.  

---

