About: Liouville Numbers and the Computational Complexity of Changing Bases

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Liouville Numbers and the Computational Complexity of Changing Bases Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : covidontheweb.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	Liouville Numbers and the Computational Complexity of Changing Bases
Creator	Jakobsen, Sune Simonsen, Jakob
Source	PMC
abstract	We study the computational complexity of uniformly converting the base-a expansion of an irrational numbers to the base-b expansion. In particular, we are interested in subsets of the irrationals where such conversion can be performed with little overhead. We show that such conversion is possible, essentially with polynomial overhead, for the set of irrationals that are not Liouville numbers. Furthermore, it is known that there are irrational numbers x such that the expansion of x in one integer base is efficiently computable, but the expansion of x in certain other integer bases is not. We prove that any such number must be a Liouville number.
has issue date	2020-06-24(xsd:dateTime)
bibo:doi	10.1007/978-3-030-51466-2_5
has license	no-cc
sha1sum (hex)	9ef6a95ad9922366947b6c9351d310638988ad00
schema:url	https://doi.org/10.1007/978-3-030-51466-2_5
resource representing a document's title	Liouville Numbers and the Computational Complexity of Changing Bases
has PubMed Central identifier	PMC7309484
schema:publication	Beyond the Horizon of Computability
resource representing a document's body	covid:9ef6a95ad9922366947b6c9351d310638988ad00#body_text
is schema:about of	named entity 'PARTICULAR' named entity 'NUMBERS' named entity 'BUT' named entity 'polynomial' named entity 'Computational Complexity' named entity 'absolutely normal number' named entity 'Liouville number' named entity 'positive reals' named entity 'Thue-Siegel-Roth theorem' named entity 'n + 1' named entity 'infinite sequence' named entity 'lookahead' named entity 'irrationality measure' named entity 'integer' named entity 'irrational number' named entity 'mutatis mutandis' named entity 'primitive recursive' named entity 'polynomial time' named entity 'irrational numbers' named entity 'unbounded search' named entity 'exponentiation' named entity 'Hausdorff dimension' named entity 'Liouville numbers' named entity 'real number' named entity 'Apéry's constant' named entity 'Martin-Löf random' named entity 'lookahead' named entity 'Turing machine' named entity 'Lemma' named entity 'rational approximations' named entity 'prime decompositions' named entity 'algorithm' named entity 'computational complexity' named entity 'computable analysis' named entity 'Hausdorff measure' named entity 'polynomial' named entity 'polynomial time' named entity 'computational complexity' named entity 'algebraic numbers' named entity 'computational complexity' named entity 'Turing machine' named entity 'positive integers' named entity 'Liouville numbers' named entity 'Mahler' named entity 'irrational number' named entity 'irrational number' named entity 'integer' named entity 'integer' named entity 'irrational number' named entity 'Turing machines' named entity 'sufficiently large' named entity 'Turing machine' named entity 'non-empty' named entity 'real numbers' named entity 'base-b' named entity 'Time and space' named entity 'non-decreasing' named entity 'total functions' named entity 'Lemma' named entity 'strictly increasing' named entity 'integer' named entity 'Lemma' named entity 'number theory' named entity 'iff' named entity 'positive reals' named entity 'rational numbers' named entity 'binary representations' named entity 'Turing machine' named entity 'Diophantine approximation' named entity 'ith' named entity 'computational complexity' named entity 'integer' named entity 'lookahead' named entity 'rational number' named entity 'Lemma 1' named entity 'arithmetic' named entity 'positive integers' named entity 'normal number' named entity 'supremum' named entity 'non-decreasing' named entity 'Grzegorczyk hierarchy' named entity 'iff'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software