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?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ I give some insight in the second part of this answer. 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. $\endgroup$– BrunoJan 5, 2018 at 13:04
-
$\begingroup$ @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 $\endgroup$– XL _At_Here_ThereJan 5, 2018 at 13:42
-
3$\begingroup$ Any algebraic number is computable in uniform $\mathrm{TC}^0$, see arxiv.org/abs/1112.3925 (Cor. 4.6). Thus, real numbers that are not computable in $\mathrm{TC}^0$ can only be transcendental. $\endgroup$– Emil JeřábekJan 5, 2018 at 13:56
-
1$\begingroup$ 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”. $\endgroup$– Emil JeřábekJan 5, 2018 at 15:54
-
2$\begingroup$ 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$. $\endgroup$– Emil JeřábekJan 5, 2018 at 20:17
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
5
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.
answered Jan 6, 2018 at 7:59
-
1$\begingroup$ 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. $\endgroup$ Jan 6, 2018 at 9:38
-
$\begingroup$ Excellent。 But Emil, you just post comment, no answer,:P $\endgroup$ Jan 6, 2018 at 10:25
-
$\begingroup$ These results can solve some problem about algebraicity and transcendentality, not so interesting, but possibly convenient $\endgroup$ Jan 7, 2018 at 2:11
-
$\begingroup$ 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. $\endgroup$ Jan 7, 2018 at 3:27
-
$\begingroup$ @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$. $\endgroup$ Jan 7, 2018 at 9:00