5
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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”). $\endgroup$
    – Emil Jeřábek
    Jun 21, 2022 at 11:08
  • $\begingroup$ My apologies I made the mistake of n in my polylog statement being the number and not the input size $\endgroup$
    – Sidharth Ghoshal
    Jun 21, 2022 at 11:25
  • $\begingroup$ See the notation here: en.m.wikipedia.org/wiki/… in section “current state of the art” $\endgroup$
    – Sidharth Ghoshal
    Jun 21, 2022 at 11:27
  • $\begingroup$ Yes, the wikipedia article misleadingly uses $n$ for the number itself rather than the length of the input. $\endgroup$
    – Emil Jeřábek
    Jun 21, 2022 at 11:30
  • $\begingroup$ What about how many primes numbers there up to n^(log(log(n))? $\endgroup$
    – Shaq
    Jun 23, 2022 at 12:20

3 Answers 3

Reset to default
11
$\begingroup$

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.

[1] Forbes, Michael A.; Saptharishi, Ramprasad; Shpilka, Amir, Hitting sets for multilinear read-once algebraic branching programs, in any order, Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 867-875 (2014). ZBL1315.68127.

Improve this answer
$\endgroup$
9
$\begingroup$

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).

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This answer is not incorrect, but to me choosing a parameter in a parameterized problem (here, the clique size) to get the time bound you want feels like cheating. $\endgroup$
    – David Eppstein
    Jul 19, 2022 at 6:31
  • $\begingroup$ For sure! That's why I said it was not that natural. But perhaps it is still useful for the OP. $\endgroup$
    – Vinicius dos Santos
    Jul 19, 2022 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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