Time complexity with irrational exponent? 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?
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.