Computing Bits of Algebraic Numbers

Details Computing Bits of Algebraic Numbers Computing Bits of Algebraic Numbers

2011-12-19

arxiv.org/abs/1112.4295v1

Computer Science

Computational Complexity

Scientific paper

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=NC1\subseteq 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.

Affiliated with

Also associated with

No associations

Rating

Computing Bits of Algebraic Numbers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing Bits of Algebraic Numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Bits of Algebraic Numbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-210531