<p>One other way to look at this, which brings in potentially all complexity classes above $\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$, is to consider real numbers in their binary expansion. Any real number whose binary expansion doesn't end with $0^\infty$ or $1^\infty$ - i.e., which is not a dyadic rational - has a unique binary expansion. We can treat this binary expansion as an element of $\{0,1\}^{\mathbb{N}}$, which in turn we can view as a subset of $\mathbb{N}$, and therefore (under the standard identification of $\mathbb{N}$ with $\Sigma^*$ for $\Sigma$ a finite alphabet) a <em>language</em>. One can then ask about the complexity of this language. (Dyadic rationals correspond to languages which are only finitely different from $\emptyset$ or from $\Sigma^*$, so aren't all that interesting anyways...)</p>

<p>Note that if a language $L$ has its characteristic function $\chi_L$ being real-time computable, then $L$ itself is in $\mathsf{E}$: given input $x$ of length $n$, suppose that $x$ is the $N$-th string in length-lexicographic order (that is, the string $x \in \Sigma^*$ corresponds to the integer $N \in \mathbb{N}$ under the standard identification). To decide whether $x \in L$, use the real-time machine to output the first $N$ bits of $\chi_L$ and read off the $N$-th bit. This takes $O(N)$ time; but $|x| = \log_{|\Sigma|} N$, so this is $O(|\Sigma|^{|x|}) = 2^{O(|x|)}$ time. </p>

<p>(As far as I can tell the converse need not hold. Or at least, the naive proof that I was thinking of doesn't work. That is, suppose $L \in \mathsf{E}$. The naive way  decide the first $N$ bits of $\chi_L$ takes $\approx N \cdot 2^{O(\log N)} = N^{1 + c}$ time for $c &gt; 0$.)</p>

<p>Using this identification, you can in principle use all complexity classes that aren't contained in $\mathsf{E}$ to try to understand the "complexity" of <s>any non-real-time-computable</s> transcendental numbers. <s>However, I don't know how to relate complexity properties of the language $L$ to whether $\chi_L$ is algebraic or transcendental. Strikes me as a very interesting question.</s> As pointed out by Emil Jerabek in the comments, using this identification, all algebraic numbers are in the linear-time version of the counting hierarchy $\mathsf{CH}$, hence also in $\mathsf{E}$. So this approach seems mainly useful for distinguishing the complexity of transcendental numbers from one another, rather than for distinguishing e.g. the complexity of real-time computable and algebraic numbers.</p>

CC BY-SA 3.0
2018-01-06T09:38:23.643Z
Well, in this setup, all algebraic numbers are in E, and also in CH. In fact, they are in the "linear-time version" of the counting hierarchy, which is included in both. This is a restatement of my comments below the question.
Emil Jeřábek
CC BY-SA 3.0
2018-01-06T10:25:37.507Z
Excellent。 But Emil, you just post comment, no answer,:P
XL _At_Here_There
CC BY-SA 3.0
2018-01-07T02:11:03.063Z
These results can solve some problem about algebraicity and transcendentality, not so interesting, but possibly convenient
XL _At_Here_There
CC BY-SA 3.0
2018-01-07T03:27:05.400Z
And, since $\pi$ is in $n log n^3$ extremely possibly, we can not separate algebraic numbers from transcendental numbers by complexity class at least now.
XL _At_Here_There
CC BY-SA 3.0
2018-01-07T09:00:34.927Z
@XL_ar_China $\pi$ is computable in time $O(M(n)\log n)$ by AGM iteration. Using the best known multiplication algorithms, this is even better than $n(\log n)^3$.
Emil Jeřábek
CC BY-SA 3.0
2018-01-06T07:59:38.860Z
2018-01-10T06:18:58.970Z
2018-01-10T06:18:58.970Z
Joshua Grochow
<p>Regarding the relation, there is the Hartmanis-Stearns conjecture, but beyond Turing Machine of the realtime output, there is no further conjecture or theorem. Obviously irrational algebraic number can not be outputted by real time TM, and so are  infinite transcendental numbers. But beyond realtime TM and in the same complexity classes like P, are there irrational algebraic numbers and transcendental numbers? Or we can separate transcendental numbers from irrational algebraic numbers by the different complexity classes?</p>

CC BY-SA 3.0
2018-01-05T13:04:56.720Z
I give *some* insight in the second part of [this answer](https://cstheory.stackexchange.com/questions/149/applications-of-tcs-to-classical-mathematics/20572#20572). It is in terms of automata though, not (TM) complexity classes. The sequence of digits is ultimately periodic for rational numbers, *automatic* for transcendental numbers and non-automatic ($\simeq$ more complex) for non-rational algebraic numbers.
Bruno
CC BY-SA 3.0
2018-01-05T13:42:56.910Z
@Bruno thank you for your comment, but I wonder if we could the relation between transcendental numbers and computational complexity, if we could separate transcendental numbers from irrational algebraic numbers by the different complexity classes
XL _At_Here_There
CC BY-SA 3.0
2018-01-05T13:56:08.790Z
Any algebraic number is computable in uniform $\mathrm{TC}^0$, see https://arxiv.org/abs/1112.3925 (Cor. 4.6). Thus, real numbers that are not computable in $\mathrm{TC}^0$ can only be transcendental.
Emil Jeřábek
CC BY-SA 3.0
2018-01-05T15:54:25.693Z
Also, in terms of sequential complexity: for any algebraic number $\alpha$, the first $n$ digits of $\alpha$ can be computed in time $n\operatorname{polylog} n$ (it’s something like $M(n)$ or $M(n)\log n$, IIRC), so they are “almost real-time”.
Emil Jeřábek
CC BY-SA 3.0
2018-01-05T20:17:04.550Z
Right, the sequential time complexity of algebraic numbers is $O(M(n))$. Just use Newton iteration, starting from a fixed good approximation. Each iteration takes $O(1)$ additions, multiplications and divisions. The number of significant digits (as well required precision of the operations) roughly doubles on each iteration, hence by the usual geometric series argument, the total time is still $O(M(n))$. Oh, and a roughly $2n$-bit approximation is enough to compute $n$ digits exactly, as algebraic numbers have irrationality measure $2$.
Emil Jeřábek
CC BY-SA 3.0
2018-01-05T23:18:49.010Z
@EmilJeřábek thank you for your helpful comment
XL _At_Here_There
<reference-request><complexity-classes><nt.number-theory><comp-number-theory>
Relation between transcendental numbers and computational complexity?
XL _At_Here_There
# Relation between transcendental numbers and computational complexity?

(Asked by: username_0 on 2018-01-05)

Regarding the relation, there is the Hartmanis-Stearns conjecture, but beyond Turing Machine of the realtime output, there is no further conjecture or theorem. Obviously irrational algebraic number can not be outputted by real time TM, and so are infinite transcendental numbers. But beyond realtime TM and in the same complexity classes like P, are there irrational algebraic numbers and transcendental numbers? Or we can separate transcendental numbers from irrational algebraic numbers by the different complexity classes?

**Tags:** reference-request, complexity-classes, nt.number-theory, comp-number-theory
> **Comments:**
> **username_1**: I give *some* insight in the second part of [this answer](https://cstheory.stackexchange.com/questions/149/applications-of-tcs-to-classical-mathematics/20572#20572). It is in terms of automata though, not (TM) complexity classes. The sequence of digits is ultimately periodic for rational numbers, *automatic* for transcendental numbers and non-automatic ($\simeq$ more complex) for non-rational algebraic numbers.  
> **username_0**: @Bruno thank you for your comment, but I wonder if we could the relation between transcendental numbers and computational complexity, if we could separate transcendental numbers from irrational algebraic numbers by the different complexity classes  
> **username_2**: Any algebraic number is computable in uniform $\mathrm{TC}^0$, see https://arxiv.org/abs/1112.3925 (Cor. 4.6). Thus, real numbers that are not computable in $\mathrm{TC}^0$ can only be transcendental.  
> **username_2**: Also, in terms of sequential complexity: for any algebraic number $\alpha$, the first $n$ digits of $\alpha$ can be computed in time $n\operatorname{polylog} n$ (it’s something like $M(n)$ or $M(n)\log n$, IIRC), so they are “almost real-time”.  
> **username_2**: Right, the sequential time complexity of algebraic numbers is $O(M(n))$. Just use Newton iteration, starting from a fixed good approximation. Each iteration takes $O(1)$ additions, multiplications and divisions. The number of significant digits (as well required precision of the operations) roughly doubles on each iteration, hence by the usual geometric series argument, the total time is still $O(M(n))$. Oh, and a roughly $2n$-bit approximation is enough to compute $n$ digits exactly, as algebraic numbers have irrationality measure $2$.  
> **username_0**: @EmilJeřábek thank you for your helpful comment  

---

## 1 answers

### Answer by username_3 on 2018-01-06. Score: 3 | Accepted answer

One other way to look at this, which brings in potentially all complexity classes above $\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$, is to consider real numbers in their binary expansion. Any real number whose binary expansion doesn't end with $0^\infty$ or $1^\infty$ - i.e., which is not a dyadic rational - has a unique binary expansion. We can treat this binary expansion as an element of $\{0,1\}^{\mathbb{N}}$, which in turn we can view as a subset of $\mathbb{N}$, and therefore (under the standard identification of $\mathbb{N}$ with $\Sigma^\*$ for $\Sigma$ a finite alphabet) a *language*. One can then ask about the complexity of this language. (Dyadic rationals correspond to languages which are only finitely different from $\emptyset$ or from $\Sigma^\*$, so aren't all that interesting anyways...)

Note that if a language $L$ has its characteristic function $\chi\_L$ being real-time computable, then $L$ itself is in $\mathsf{E}$: given input $x$ of length $n$, suppose that $x$ is the $N$-th string in length-lexicographic order (that is, the string $x \in \Sigma^\*$ corresponds to the integer $N \in \mathbb{N}$ under the standard identification). To decide whether $x \in L$, use the real-time machine to output the first $N$ bits of $\chi\_L$ and read off the $N$-th bit. This takes $O(N)$ time; but $|x| = \log\_{|\Sigma|} N$, so this is $O(|\Sigma|^{|x|}) = 2^{O(|x|)}$ time.

(As far as I can tell the converse need not hold. Or at least, the naive proof that I was thinking of doesn't work. That is, suppose $L \in \mathsf{E}$. The naive way decide the first $N$ bits of $\chi\_L$ takes $\approx N \cdot 2^{O(\log N)} = N^{1 + c}$ time for $c > 0$.)

Using this identification, you can in principle use all complexity classes that aren't contained in $\mathsf{E}$ to try to understand the "complexity" of ~~any non-real-time-computable~~ transcendental numbers. ~~However, I don't know how to relate complexity properties of the language $L$ to whether $\chi\_L$ is algebraic or transcendental. Strikes me as a very interesting question.~~ As pointed out by Emil Jerabek in the comments, using this identification, all algebraic numbers are in the linear-time version of the counting hierarchy $\mathsf{CH}$, hence also in $\mathsf{E}$. So this approach seems mainly useful for distinguishing the complexity of transcendental numbers from one another, rather than for distinguishing e.g. the complexity of real-time computable and algebraic numbers.

> **Comments:**
> **username_2**: Well, in this setup, all algebraic numbers are in E, and also in CH. In fact, they are in the "linear-time version" of the counting hierarchy, which is included in both. This is a restatement of my comments below the question.  
> **username_0**: Excellent。 But Emil, you just post comment, no answer,:P  
> **username_0**: These results can solve some problem about algebraicity and transcendentality, not so interesting, but possibly convenient  
> **username_0**: And, since $\pi$ is in $n log n^3$ extremely possibly, we can not separate algebraic numbers from transcendental numbers by complexity class at least now.  
> **username_2**: @XL_ar_China $\pi$ is computable in time $O(M(n)\log n)$ by AGM iteration. Using the best known multiplication algorithms, this is even better than $n(\log n)^3$.  

---

