2
$\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?

$\endgroup$
5
  • $\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$ Jun 21 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$ Jun 21 at 11:25
  • $\begingroup$ See the notation here: en.m.wikipedia.org/wiki/… in section “current state of the art” $\endgroup$ Jun 21 at 11:27
  • $\begingroup$ Yes, the wikipedia article misleadingly uses $n$ for the number itself rather than the length of the input. $\endgroup$ Jun 21 at 11:30
  • $\begingroup$ What about how many primes numbers there up to n^(log(log(n))? $\endgroup$
    – Shaq
    Jun 23 at 12:20

2 Answers 2

7
$\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.

$\endgroup$
4
$\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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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