On the definitions of some complexity classes of real numbers

DOI10.1007/BF01744572MaRDI QIDQ3310597zbMATH OpenOpenAlexFDO

Authors Ker-I Ko

Publication date 1983

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01744572

zbMATH Keywords

binary expansionsCauchy sequencescomplexity-bounded classes of real numberscomputable real numberDedekind cutsrecursively enumerable real numbersreducibilities

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Constructive and recursive analysis (03F60)

Cites work

• A comparison of polynomial time reducibilities
• Computational complexity of real functions
• scientific article; zbMATH DE number 3144512 (Why is no real title available?)
• scientific article; zbMATH DE number 3471606 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Nicht konstruktiv beweisbare Sätze der Analysis
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On computable sequences
• Recursive Real Numbers
• Separating Nondeterministic Time Complexity Classes
• Some observations on NP real numbers and P-selective sets
• Tally languages and complexity classes
• The maximum value problem and NP real numbers
• The polynomial-time hierarchy

Cited in

(28)

• Approximation to measurable functions and its relation to probabilistic computation
• On the continued fraction representation of computable real numbers
• Representations of the real numbers and of the open subsets of the set of real numbers
• The maximum value problem and NP real numbers
• Some observations on NP real numbers and P-selective sets
• Average case completeness
• A note of best fractions of a computable real number
• Complete distributional problems, hard languages, and resource-bounded measure
• Rational presented metric spaces and complexity, the case of the space of real functions uniformly continuous on a compact interval
• Complexity of the calculus of continued fraction representation of real numbers
• On the computational complexity of best Chebyshev approximations
• Using PVS to validate the algorithms of an exact arithmetic.
• Randomness and reducibility
• On the complexity of conversion between classic real number representations
• Dedekind cuts and long strings of zeros in base expansions
• Computable irrational numbers with representations of surprising complexity
• In Memoriam: Ker-I Ko (1950–2018)
• On the complexity of computable real sequences
• Primitive recursiveness of real numbers under different representations
• Computability of Real Numbers
• The computational complexity of distance functions of two-dimensional domains
• Weakly computable real numbers
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
• Interplay between insertion of zeros and the complexity of Dedekind cuts
• Real numbers, continued fractions and complexity classes
• Reducibilities on real numbers
• Probabilistic Turing machines and recursively enumerable Dedekind cuts
• Représentations des nombres réels par développements en base entière et complexité. (Representations of real numbers by expansions on integer basis and complexity)

This page was built for publication: On the definitions of some complexity classes of real numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3310597)