<p>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. </p>

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

<p>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.</p>

CC BY-SA 3.0
2015-09-27T12:49:23.737Z
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$.
Yuval Filmus
CC BY-SA 3.0
2015-09-27T16:31:44.353Z
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.
Huck Bennett
CC BY-SA 3.0
2015-09-28T07:13:31.083Z
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.
Joe Bebel
CC BY-SA 3.0
2015-09-28T08:16:00.413Z
Some integer multiplication algorithms have irrational exponents if I remember correctly.
Yuval Filmus
CC BY-SA 3.0
2015-09-28T08:24:52.077Z
Right, like Karatsuba's. But it's still multiplication :)
Joe Bebel
CC BY-SA 3.0
2015-09-27T00:27:19.593Z
2015-09-27T00:27:19.593Z
Joe Bebel
<p>Is there any natural problem in <strong>P</strong> for which the best known running time bound is of the form $O(n^\alpha)$, where $\alpha$ is an <em>irrational</em> constant?</p>

CC BY-SA 3.0
2015-09-26T23:28:05.507Z
Neat question!  :)
Michael Wehar
CC BY-SA 3.0
2015-09-27T23:56:11.870Z
see also [golden ratio or $\pi$ in the running time](http://cstheory.stackexchange.com/questions/14999/golden-ratio-or-pi-in-the-running-time). this could conceivably be a [tag:big-list]...
vzn
CC BY-SA 3.0
2015-09-28T17:31:48.280Z
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.
KWillets
<cc.complexity-theory><time-complexity><polynomial-time>
Time complexity with irrational exponent?
Andras Farago
# Time complexity with irrational exponent?

(Asked by: username_0 on 2015-09-26)

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?

**Tags:** cc.complexity-theory, time-complexity, polynomial-time
> **Comments:**
> **username_1**: Neat question!  :)  
> **username_2**: see also [golden ratio or $\pi$ in the running time](http://cstheory.stackexchange.com/questions/14999/golden-ratio-or-pi-in-the-running-time). this could conceivably be a [tag:big-list]...  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2015-09-27. Score: 21 | Accepted answer

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.

> **Comments:**
> **username_5**: 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$.  
> **username_6**: 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.  
> **username_4**: 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.  
> **username_5**: Some integer multiplication algorithms have irrational exponents if I remember correctly.  
> **username_4**: Right, like Karatsuba's. But it's still multiplication :)  

---

