# Are there any problems whose best known algorithms have running time $n^{\log \log n}$?

It’s well known that problems such as integer factorization have running times contained in $$e^{\text{Poly} \log }$$ which is the same $$n^{ \text{Poly} \log }$$ (actually the log term is itself in a cube root for integer factorization)

So this got me wondering about complexity classes that live between polynomial time and $$e^{\text{Poly} \log }$$ namely $$e^{\log \cdot \text{Poly} \log \log }$$ or $$n^{\text{Poly} \log \log}$$ as the title puts it.

Are there any problems whose best known algorithms live in this runtime complexity?

• Integer factorization is most certainly not known to have quasipolynomial-time ($n^{(\log n)^c}$) algorithms. This would break a lot of public key cryptography, for a start. The best known factoring algorithms are exponential-time ($2^{n^\epsilon}$, for $\epsilon\approx1/3$; some people falsely advertize this as “subexponential”). Jun 21, 2022 at 11:08
• My apologies I made the mistake of n in my polylog statement being the number and not the input size Jun 21, 2022 at 11:25
• See the notation here: en.m.wikipedia.org/wiki/… in section “current state of the art” Jun 21, 2022 at 11:27
• Yes, the wikipedia article misleadingly uses $n$ for the number itself rather than the length of the input. Jun 21, 2022 at 11:30
• What about how many primes numbers there up to n^(log(log(n))?
– Shaq
Jun 23, 2022 at 12:20

The best-known deterministic algorithm for testing polynomial identities given by depth-three diagonal circuits has running time $$n^{O(\log \log n)}$$ [1].
More explicitly, we are given an expression of the form $$f(x_1,\ldots,x_n) = \sum_{i=1}^s (a_{i,0} + a_{i,1} x_1 + \cdots + a_{i,n} x_n)^{d_i}$$ and we want to test if $$f(x_1,\ldots,x_n)$$ is the identically zero polynomial. Forbes, Shpilka, and Saptharishi gave a deterministic algorithm for this problem that runs in time $$\mathsf{poly}(n,d,s)^{O(\log \log (ds))}$$, where $$d = \max_{i\in [s]}d_i$$. Of course, it is conjectured that polynomial identity testing can be solved in deterministic polynomial time, so this is unlikely to be the best possible deterministic algorithm for this problem.
The best-known algorithm for testing isomorphism of finite groups whose solvable radical is either (a) contained in the center or (b) elementary abelian, is $$n^{O(\log \log n)}$$. These are, respectively, Theorems A and B of my paper with Youming Qiao. In this case, the bound comes from enumerating the automorphisms of $$G/Rad(G)$$, which is a group with no abelian normal subgroups (aka Fitting-free or semisimple). The number of such automorphisms can indeed be as large as $$n^{\Theta(\log \log n)}$$ (e.g. if $$G/Rad(G) \cong A_5^k$$ where $$k = \Theta(\log |G|)$$). Improving this upper bound to $$n^{o(\log \log n)}$$ thus requires a new strategy (my guess would be that it's doable though).
Probably not as interesting or natural such as the problems mentioned in the previous answers, another problem that would fit in your question in the one of finding a clique of size $$\log\log n$$ in a graph with $$n$$ vertices. And I believe that, under some standard parameterized complexity assumptions, this cannot be improved.