Paper Info
Title
On logarithmic-space computable real numbers
Abstract
We study, in this paper, the relationship among the classes of logarithmic-space computable real numbers under different representations. We consider logarithmic-space computable real numbers under the Cauchy function representation, the general left cut representation, the standard left cut representation, and the binary expansion representation. It is shown that the relationship among these classes of real numbers depends on the relationship between the discrete complexity classes P"1 and L"1, the classes of tally sets in P and L, respectively. First, if P"1=L"1, then the relationship among the four classes of logarithmic-space computable real numbers is the same as that among these classes of polynomial-time computable real numbers. On the other hand, if P"1L"1, then we get different relationships from those among classes of polynomial-time computable real numbers. For instance, while the classes of polynomial-time computable real numbers under the general left cut and the Cauchy function representations are equivalent, we show, under the assumption of P"1L"1, that the class of logarithmic-space computable real numbers under the general left cut representation properly contains the class of logarithmic-space computable real numbers under the Cauchy function representation. In addition, if P"1L"1, then the two classes of logarithmic-space computable real numbers under the standard left cut and the Cauchy function representations are incomparable.
Year
DOI
Venue
2013
10.1016/j.tcs.2012.10.004
Theor. Comput. Sci.
Keywords
DocType
Volume
logarithmic-space computable real number,real number,different relationship,discrete complexity class,tally set,Cauchy function representation,different representation,binary expansion representation,polynomial-time computable real number
Journal
469,
ISSN
Citations 
PageRank 
0304-3975
1
0.40
References 
Authors
5
2
Name
Order
Citations
PageRank
Fuxiang Yu1194.83
Ker-I Ko219628.54