21
$\begingroup$

Is there any natural problem in P for which the best known running time bound is of the form $O(n^\alpha)$, where $\alpha$ is an irrational constant?

$\endgroup$
  • 4
    $\begingroup$ Neat question! :) $\endgroup$ – Michael Wehar Sep 26 '15 at 23:28
  • 1
    $\begingroup$ see also golden ratio or $\pi$ in the running time. this could conceivably be a big-list... $\endgroup$ – vzn Sep 27 '15 at 23:56
  • $\begingroup$ Sorting a multiset is around nH+n, so if you could get H (entropy) to converge to some $n^{\alpha-1}$ that would technically qualify. I wouldn't call that "natural" though. However there might be some more natural problem where the input is reduced in this way. $\endgroup$ – KWillets Sep 28 '15 at 17:31
22
$\begingroup$

While admittedly I haven't done the analysis, and this is not strictly a decision problem, I am willing to wager the best known matrix multiplication algorithms (by Coppersmith, Winograd, Stothers, Williams, et al) have irrational exponent.

This can be seen more clearly in the simple case of Strassen's algorithm, which has running time $O(n^{\log_2 7})$.

And, this is not precisely what you asked, but Ryan Williams has shown that all algorithms that solve SAT in space $n^{o(1)}$ require time $n^{2 \cos(\pi/7) - o(1)}$, which is another interesting and unusual appearance of an irrational constant in TCS.

$\endgroup$
  • 3
    $\begingroup$ Algorithms beyond Strassen's algorithm don't really run in $O(n^\alpha)$ for their stated exponent $\alpha$. Rather, for every $\epsilon > 0$ they run in $O_\epsilon(n^{\alpha+\epsilon})$. This is due to several limits involved in obtaining $\alpha$. $\endgroup$ – Yuval Filmus Sep 27 '15 at 12:49
  • 12
    $\begingroup$ The time complexity of Strassen's algorithm is really an artifact of a Master recurrence $T(n) = a T(n/b) + f(n)$ solving to $\Theta(n^{\log_b a})$. You can come up with many of your favorite irrational numbers by instantiating $a$ and $b$ with different values. $\endgroup$ – Huck Bennett Sep 27 '15 at 16:31
  • $\begingroup$ Yes, I agree with both. I figured I was already being loose with the definition of P, and having not actually checked if the matrix multiplication exponents are irrational. Although I would be surprised if they were rational, given how they are derived. Deep down, fast matrix multiplications still echo Strassen's basic divide and conquer method, though it is described in tensor language now. Actually, though it is easy to construct algorithms as you describe with irrational $\log_b a$, I cannot think of any other natural divide and conquer algorithm with such property, besides multiplication. $\endgroup$ – Joe Bebel Sep 28 '15 at 7:13
  • $\begingroup$ Some integer multiplication algorithms have irrational exponents if I remember correctly. $\endgroup$ – Yuval Filmus Sep 28 '15 at 8:16
  • $\begingroup$ Right, like Karatsuba's. But it's still multiplication :) $\endgroup$ – Joe Bebel Sep 28 '15 at 8:24

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.