Computing bits of algebraic numbers
From MaRDI portal
Abstract: We initiate the complexity theoretic study of the problem of computing the bits of (real) algebraic numbers. This extends the work of Yap on computing the bits of transcendental numbers like pi, in Logspace. Our main result is that computing a bit of a fixed real algebraic number is in C=NC1subseteq Logspace when the bit position has a verbose (unary) representation and in the counting hierarchy when it has a succinct (binary) representation. Our tools are drawn from elementary analysis and numerical analysis, and include the Newton-Raphson method. The proof of our main result is entirely elementary, preferring to use the elementary Liouville's theorem over the much deeper Roth's theorem for algebraic numbers. We leave the possibility of proving non-trivial lower bounds for the problem of computing the bits of an algebraic number given the bit position in binary, as our main open question. In this direction we show very limited progress by proving a lower bound for rationals.
Recommendations
- Computing partial information out of intractable: powers of algebraic numbers as an example
- Complexity of computation on real algebraic numbers
- Fields of algebraic numbers computable in polynomial time. I
- NC algorithms for real algebraic numbers
- Polynomial-time presentations of algebraic number fields
Cited in
(4)- On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
- Hamiltonian complexity in the thermodynamic limit
- Computation of algebraic numbers and arithmetic operations over them with linear memory
- Computing partial information out of intractable: powers of algebraic numbers as an example
This page was built for publication: Computing bits of algebraic numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2898030)
