Reducibilities on real numbers

DOI10.1016/0304-3975(84)90129-4zbMath0542.03033OpenAlexW1994458535MaRDI QIDQ795039

Ker-I. Ko

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90129-4

zbMATH Keywords

reducibilitypolynomial-timeCauchy sequence representationrecursive real functionstruth-table oracle Turing machine

Mathematics Subject Classification ID

Constructive and recursive analysis (03F60) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10)

Related Items

In Memoriam: Ker-I Ko (1950–2018), Unnamed Item, \(\delta\)-uniform BSS machines, The Turing closure of an Archimedean field, Equality is a jump, The closure properties on real numbers under limits and computable operators.

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• On computable sequences
• On the definitions of some complexity classes of real numbers
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Recursion Theory and Dedekind Cuts
• Nicht konstruktiv beweisbare Sätze der Analysis
• Recursive Real Numbers