Reducibilities on real numbers

DOI10.1016/0304-3975(84)90129-4MaRDI QIDQ795039zbMATH OpenOpenAlexFDO

Authors 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

Cauchy sequence representationpolynomial-timerecursive real functionsreducibilitytruth-table oracle Turing machine

Mathematics Subject Classification ID

Turing machines and related notions (03D10) 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) Constructive and recursive analysis (03F60)

Review text

The structure of recursive real functions is investigated through the notion of reducibility. The main result is that a recursive real function f maps a real number x to a real number y if and only if x is truth-table reducible to y in the sense that there is a truth-table oracle Turing machine M that computes a Cauchy sequence representation of x whenever a Cauchy sequence representation of y is given as an oracle. (An oracle Turing machine M is truth-table if the queries made by M depend only on the input and are independent of the oracle.) Other results include: a monotonic increasing recursive real function f maps x to y iff x is many- one reducible to y; a polynomial-time computable real function f maps x to y iff x is polynomial-time Turing reducible to y; and a monotonic increasing, polynomial-time computable real function f maps x to y iff x is polynomial-time many-one reducible to y. Questions are asked to find a characterization, in terms of the notion of reducibility, of the pairs of real numbers (x,y) for which there exist differential, recursive real functions f mapping x to y.

Recommendations

• scientific article; zbMATH DE number 4053594
• On the Definition of Computable Function of a Real Variable
• Relatively recursive reals and real functions
• Strong polynomial-time reducibility
• Relativization of Real Numbers to a Universe

Cites work

• A comparison of polynomial time reducibilities
• Computational complexity of real functions
• scientific article; zbMATH DE number 3143694 (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 sequences
• On the definitions of some complexity classes of real numbers
• Recursion Theory and Dedekind Cuts
• Recursive Real Numbers
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Some observations on NP real numbers and P-selective sets
• The maximum value problem and NP real numbers

Cited in

(12)

• \(\delta\)-uniform BSS machines
• Equality is a jump
• Real reduction theory
• The Turing closure of an Archimedean field
• The closure properties on real numbers under limits and computable operators.
• In Memoriam: Ker-I Ko (1950–2018)
• Reducibility in A_ℝ(K), C_ℝ(K), and A(K)
• scientific article; zbMATH DE number 4053594 (Why is no real title available?)
• On reduction properties
• scientific article; zbMATH DE number 1747708 (Why is no real title available?)
• scientific article; zbMATH DE number 1929453 (Why is no real title available?)
• On the group of computable automorphisms of the linear order of the reals

This page was built for publication: Reducibilities on real numbers

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