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?
$\begingroup$
$\endgroup$
3
-
4$\begingroup$ Neat question! :) $\endgroup$– Michael WeharCommented Sep 26, 2015 at 23:28
-
1$\begingroup$ see also golden ratio or $\pi$ in the running time. this could conceivably be a big-list... $\endgroup$– vznCommented Sep 27, 2015 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$– KWilletsCommented Sep 28, 2015 at 17:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
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$ Commented Sep 27, 2015 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$ Commented Sep 27, 2015 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$ Commented Sep 28, 2015 at 7:13
-
$\begingroup$ Some integer multiplication algorithms have irrational exponents if I remember correctly. $\endgroup$ Commented Sep 28, 2015 at 8:16
-
$\begingroup$ Right, like Karatsuba's. But it's still multiplication :) $\endgroup$ Commented Sep 28, 2015 at 8:24