Reducibilities on real numbers
From MaRDI portal
Publication:795039
DOI10.1016/0304-3975(84)90129-4zbMath0542.03033OpenAlexW1994458535MaRDI QIDQ795039
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
reducibilitypolynomial-timeCauchy sequence representationrecursive real functionstruth-table oracle Turing machine
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