<p>VC-dimension of set systems is known to be quasipolynomial but not known to be polynomial, with some evidence (based on the strong exponential time hypothesis) that it is not polynomial.</p>
<p>See:</p>
<p>Linial, Nathan, Mansour, Yishay, and Rivest, Ronald L. (1991), “Results on learnability and the Vapnik–Chervonenkis dimension”, Inf. Comput. 90 (1): 33–49.</p>
<p>Manurangsi, Pasin, and Rubinstein, Aviad (2017), “Inapproximability of VC dimension and Littlestone’s dimension”, Proc. 2017 Conf. Learning Theory (COLT 2017), Proceedings of Machine Learning Research 65, pp. 1432–1460.</p>
<p>Papadimitriou, Christos H., and Yannakakis, Mihalis (1996), “On limited nondeterminism and the complexity of the V–C dimension”, J. Comput. Syst. Sci. 53 (2): 161–170.</p>

CC BY-SA 4.0
2020-06-20T17:44:32.877Z
2020-06-20T17:44:32.877Z
David Eppstein
<p>Minimum dominating set in tournaments problem has quasi-polynomial time algorithm (hence sub-exponential). There is no known polynomial time algorithm for it. <a href="http://www.sciencedirect.com/science/article/pii/0304397588901314" rel="noreferrer">Tournament dominating set</a> has polynomial-time algorithm if and only if SAT has sub-exponential time algorithm. Therefore, the  exponential time hypothesis (ETH) implies that tournament dominating set can not have polynomial time algorithm. Furthermore, ETH implies that tournament dominating set is in <span class="math-container">$NP$</span>-intermediate.</p>

CC BY-SA 4.0
2020-06-20T16:26:22.987Z
2020-06-20T17:02:53.517Z
2020-06-20T17:02:53.517Z
Mohammad Al-Turkistany
<p>Parity games have recently been shown to be solvable in quasipolynomial time: <a href="https://doi.org/10.1137/17M1145288" rel="noreferrer">https://doi.org/10.1137/17M1145288</a></p>

CC BY-SA 4.0
2020-06-20T17:06:48.937Z
2020-06-20T17:06:48.937Z
Hermann Gruber
<h2>Factoring integers</h2>
<p>The <a href="https://en.wikipedia.org/wiki/General_number_field_sieve" rel="nofollow noreferrer">General Number Field Sieve</a> is known to be sub-exponential in the size of the input, for example see this quote from the link I just gave:</p>
<blockquote>
<p>The running time of the number field sieve is super-polynomial but
sub-exponential in the size of the input.</p>
</blockquote>
<p>However no polynomial-time algorithm for factoring integers is known (yet).</p>

CC BY-SA 4.0
2020-06-23T06:46:31.477Z
The running time of the algorithm is (up to less significant factors) $2^{n^\epsilon}$ for some constant $\epsilon>0$. More often than not, bounds of this form are considered *exponential* in complexity theory. See also https://cs.stackexchange.com/a/9814.
Emil Jeřábek
CC BY-SA 4.0
2020-06-22T23:03:43.230Z
2020-06-22T23:03:43.230Z
user1271772
<p><a href="https://arxiv.org/abs/1906.10668" rel="nofollow noreferrer">Discrete log in multiplicative groups of finite fields of small characteristic has quasi-polynomial running time</a>. Specifically, for <span class="math-container">$\mathbb{F}_{p^n}^\times$</span> (where inputs have size <span class="math-container">$\log_2(p^n) = n\log_2(p)$</span>) the (expected) running time is <span class="math-container">$(pn)^{2\log_2(n) + O(1)} = 2^{2\log_2(p)\log_2(n) + O(1) + 2 \log_2(n)^2 + O(\log_2(n))} = 2^{O(\log_2(n)^2)}$</span></p>

CC BY-SA 4.0
2020-06-23T14:49:42.317Z
2020-06-23T14:49:42.317Z
Mark Schultz-Wu
<ol>
<li><p>Problems in <span class="math-container">$NTIME[f(n)]$</span> where <span class="math-container">$f(n)=\omega(\log n)$</span> and <span class="math-container">$f(n)=o(n)$</span> are not known to be in <span class="math-container">$DTIME[n^c]$</span> at any <span class="math-container">$c\geq1$</span> while known to be in <span class="math-container">$DTIME[2^{o(n)}]$</span>.</p>
</li>
<li><p>Conversely there are problems not known to be in <span class="math-container">$NTIME[f(n)]$</span> where <span class="math-container">$f(n)=\omega(\log n)$</span> and <span class="math-container">$f(n)=o(n)$</span> and also not known to be in <span class="math-container">$DTIME[n^c]$</span> at any <span class="math-container">$c\geq1$</span> while known to be in <span class="math-container">$DTIME[2^{o(n)}]$</span>.</p>
</li>
</ol>
<p>Examples of <span class="math-container">$2$</span> include factoring and discrete logarithm.</p>

CC BY-SA 4.0
2020-06-23T20:16:14.413Z
For item 1, if $f(n)=o(n)$, then it seems like the machine does not have enough time to read all of its input bits. Perhaps I am missing something? Maybe the model is something other than a standard Turing Machine, e.g. a word RAM Turing Machine?
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2020-06-30T01:21:42.290Z
In computational complexity theory, the complexity class $NTIME(f(n))$ is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time $O(f(n))$. Nothing more.
VS.
CC BY-SA 4.0
2020-06-23T11:36:31.007Z
2020-06-23T11:36:31.007Z
VS.
<p>Graph Isomorphism is known to be in quasipolynomial time but not known to be in polynomial time: <a href="https://arxiv.org/abs/1512.03547" rel="noreferrer">https://arxiv.org/abs/1512.03547</a></p>
<p>You can also come up with synthetic problems by the time hierarchy theorem, which essentially states that there are problems at any (deterministic) time complexity but not below: <a href="https://en.wikipedia.org/wiki/Time_hierarchy_theorem" rel="noreferrer">https://en.wikipedia.org/wiki/Time_hierarchy_theorem</a></p>

CC BY-SA 4.0
2020-06-20T16:04:29.527Z
2020-06-20T16:04:29.527Z
Mahdi Cheraghchi
<p>What are examples of problems that are known to be sub-exponential, but</p>
<ol>
<li>are known to be non-polynomial, or</li>
<li>are not known to be polynomial?</li>
</ol>
<p><strong>EDIT.</strong> Here is what I mean by sub-exponential (apologies for leaving this open). A function <span class="math-container">$f:\mathbb{N}\to\mathbb{N}$</span> is <em>subexponential</em> if <span class="math-container">$$f(n) = 2^{n^{o(1)}}.$$</span> (Thanks to Emil Jerabek for his help in the comment section below!)</p>

CC BY-SA 4.0
2020-06-21T04:20:58.183Z
It's good to clarify what you mean by sub-exponential. See also https://cs.stackexchange.com/questions/9813/are-there-subexponential-time-algorithms-for-np-complete-problems
usul
CC BY-SA 4.0
2020-06-21T04:23:54.657Z
If the author means subexponential as in **III.** from the resource in the above comment, then I have a feeling some studied Exponential-time Complete problems would also meet the criteria.
Michael Wehar
CC BY-SA 4.0
2020-06-23T12:08:46.530Z
Yes, this is very nonstandard. This makes $2^n$ subexponential.
Emil Jeřábek
CC BY-SA 4.0
2020-06-23T12:46:48.847Z
@DominicvanderZypen $\frac1me^n=\Omega(2^n)$.
VS.
CC BY-SA 4.0
2020-06-24T06:44:16.630Z
@EmilJeřábek Sorry, right, tried to amend it
Dominic van der Zypen
CC BY-SA 4.0
2020-06-24T06:59:02.717Z
The new definition is hard to decipher, but is actually equivalent to just $f(n)=2^{o(n)}$. Why don’t you write it that way? (And while this is not nonstandard, in complexity theory this definition is less common and less convenient than the more natural definition $f(n)=2^{n^{o(1)}}$, which is robust wrt polynomial changes in the representation of the input or in the parameter to specify the problem. E.g., according to your definition, brute force $2^{O(|V|)}$  algorithms for the maximum independent set and similar graph problems are “subexponential” as the size of the input is $|V|^2$.)
Emil Jeřábek
CC BY-SA 4.0
2020-06-24T07:01:39.177Z
OK - having digested the definition of $o(\cdot)$ I see your point and will make the post more readable.
Dominic van der Zypen
<cc.complexity-theory>
In the neutral zone between polynomial and sub-exponential
Dominic van der Zypen
# In the neutral zone between polynomial and sub-exponential

(Asked by: username_0 on 2020-06-20)

What are examples of problems that are known to be sub-exponential, but

1. are known to be non-polynomial, or
2. are not known to be polynomial?

**EDIT.** Here is what I mean by sub-exponential (apologies for leaving this open). A function $f:\mathbb{N}\to\mathbb{N}$ is *subexponential* if $$f(n) = 2^{n^{o(1)}}.$$ (Thanks to Emil Jerabek for his help in the comment section below!)

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: It's good to clarify what you mean by sub-exponential. See also https://cs.stackexchange.com/questions/9813/are-there-subexponential-time-algorithms-for-np-complete-problems  
> **username_2**: If the author means subexponential as in **III.** from the resource in the above comment, then I have a feeling some studied Exponential-time Complete problems would also meet the criteria.  
> **username_3**: Yes, this is very nonstandard. This makes $2^n$ subexponential.  
> **username_4**: @DominicvanderZypen $\frac1me^n=\Omega(2^n)$.  
> **username_0**: @EmilJeřábek Sorry, right, tried to amend it  
> **username_3**: The new definition is hard to decipher, but is actually equivalent to just $f(n)=2^{o(n)}$. Why don’t you write it that way? (And while this is not nonstandard, in complexity theory this definition is less common and less convenient than the more natural definition $f(n)=2^{n^{o(1)}}$, which is robust wrt polynomial changes in the representation of the input or in the parameter to specify the problem. E.g., according to your definition, brute force $2^{O(|V|)}$  algorithms for the maximum independent set and similar graph problems are “subexponential” as the size of the input is $|V|^2$.)  
> **username_0**: OK - having digested the definition of $o(\cdot)$ I see your point and will make the post more readable.  

---

## 7 answers

### Answer by username_11 on 2020-06-20. Score: 19 | Accepted answer

Graph Isomorphism is known to be in quasipolynomial time but not known to be in polynomial time: <https://arxiv.org/abs/1512.03547>

You can also come up with synthetic problems by the time hierarchy theorem, which essentially states that there are problems at any (deterministic) time complexity but not below: <https://en.wikipedia.org/wiki/Time_hierarchy_theorem>


---

### Answer by username_5 on 2020-06-20. Score: 16

VC-dimension of set systems is known to be quasipolynomial but not known to be polynomial, with some evidence (based on the strong exponential time hypothesis) that it is not polynomial.

See:

Linial, Nathan, Mansour, Yishay, and Rivest, Ronald L. (1991), “Results on learnability and the Vapnik–Chervonenkis dimension”, Inf. Comput. 90 (1): 33–49.

Manurangsi, Pasin, and Rubinstein, Aviad (2017), “Inapproximability of VC dimension and Littlestone’s dimension”, Proc. 2017 Conf. Learning Theory (COLT 2017), Proceedings of Machine Learning Research 65, pp. 1432–1460.

Papadimitriou, Christos H., and Yannakakis, Mihalis (1996), “On limited nondeterminism and the complexity of the V–C dimension”, J. Comput. Syst. Sci. 53 (2): 161–170.


---

### Answer by username_6 on 2020-06-20. Score: 11

Minimum dominating set in tournaments problem has quasi-polynomial time algorithm (hence sub-exponential). There is no known polynomial time algorithm for it. [Tournament dominating set](http://www.sciencedirect.com/science/article/pii/0304397588901314) has polynomial-time algorithm if and only if SAT has sub-exponential time algorithm. Therefore, the exponential time hypothesis (ETH) implies that tournament dominating set can not have polynomial time algorithm. Furthermore, ETH implies that tournament dominating set is in $NP$-intermediate.


---

### Answer by username_7 on 2020-06-20. Score: 11

Parity games have recently been shown to be solvable in quasipolynomial time: <https://doi.org/10.1137/17M1145288>


---

### Answer by username_8 on 2020-06-22. Score: 2

## Factoring integers

The [General Number Field Sieve](https://en.wikipedia.org/wiki/General_number_field_sieve) is known to be sub-exponential in the size of the input, for example see this quote from the link I just gave:

> The running time of the number field sieve is super-polynomial but
> sub-exponential in the size of the input.

However no polynomial-time algorithm for factoring integers is known (yet).

> **Comments:**
> **username_3**: The running time of the algorithm is (up to less significant factors) $2^{n^\epsilon}$ for some constant $\epsilon>0$. More often than not, bounds of this form are considered *exponential* in complexity theory. See also https://cs.stackexchange.com/a/9814.  

---

### Answer by username_9 on 2020-06-23. Score: 1

[Discrete log in multiplicative groups of finite fields of small characteristic has quasi-polynomial running time](https://arxiv.org/abs/1906.10668). Specifically, for $\mathbb{F}\_{p^n}^\times$ (where inputs have size $\log\_2(p^n) = n\log\_2(p)$) the (expected) running time is $(pn)^{2\log\_2(n) + O(1)} = 2^{2\log\_2(p)\log\_2(n) + O(1) + 2 \log\_2(n)^2 + O(\log\_2(n))} = 2^{O(\log\_2(n)^2)}$


---

### Answer by username_4 on 2020-06-23. Score: -1

1. Problems in $NTIME[f(n)]$ where $f(n)=\omega(\log n)$ and $f(n)=o(n)$ are not known to be in $DTIME[n^c]$ at any $c\geq1$ while known to be in $DTIME[2^{o(n)}]$.
2. Conversely there are problems not known to be in $NTIME[f(n)]$ where $f(n)=\omega(\log n)$ and $f(n)=o(n)$ and also not known to be in $DTIME[n^c]$ at any $c\geq1$ while known to be in $DTIME[2^{o(n)}]$.

Examples of $2$ include factoring and discrete logarithm.

> **Comments:**
> **username_10**: For item 1, if $f(n)=o(n)$, then it seems like the machine does not have enough time to read all of its input bits. Perhaps I am missing something? Maybe the model is something other than a standard Turing Machine, e.g. a word RAM Turing Machine?  
> **username_4**: In computational complexity theory, the complexity class $NTIME(f(n))$ is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time $O(f(n))$. Nothing more.  

---

