On the definitions of some complexity classes of real numbers

DOI10.1007/BF01744572zbMath0529.03016OpenAlexW2020164082MaRDI QIDQ3310597

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

Cauchy sequencescomputable real numberDedekind cutsreducibilitiesbinary expansionscomplexity-bounded classes of real numbersrecursively enumerable real numbers

Mathematics Subject Classification ID

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

Related Items

Randomness and reducibility, 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, On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1, On the complexity of computable real sequences, The maximum value problem and NP real numbers, Some observations on NP real numbers and P-selective sets, Computable irrational numbers with representations of surprising complexity, Average case completeness, In Memoriam: Ker-I Ko (1950–2018), A note of best fractions of a computable real number, Weakly computable real numbers, Primitive Recursiveness of Real Numbers under Different Representations, The computational complexity of distance functions of two-dimensional domains, Real numbers, continued fractions and complexity classes, Complexity of the calculus of continued fraction representation of real numbers, On the computational complexity of best Chebyshev approximations, 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, Reducibilities on real numbers, Using PVS to validate the algorithms of an exact arithmetic., 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), On the complexity of conversion between classic real number representations, Computability of Real Numbers, Dedekind cuts and long strings of zeros in base expansions

Cites Work

• The maximum value problem and NP real numbers
• Some observations on NP real numbers and P-selective sets
• Computational complexity of real functions
• A comparison of polynomial time reducibilities
• The polynomial-time hierarchy
• On computable sequences
• Separating Nondeterministic Time Complexity Classes
• Tally languages and complexity classes
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Nicht konstruktiv beweisbare Sätze der Analysis
• Recursive Real Numbers
• Unnamed Item
• Unnamed Item
• Unnamed Item