Reducibilities on real numbers
type: Item
instance of: scholarly article
title: Reducibilities on real numbers
zbMATH Open document ID: 0542.03033
DOI: 10.1016/0304-3975(84)90129-4
published in: Theoretical Computer Science
publication date: 1984-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 03F60
Mathematics Subject Classification ID: 03D20
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D10
zbMATH DE Number: 3861147
zbMATH Keywords: recursive real functions
zbMATH Keywords: reducibility
zbMATH Keywords: truth-table oracle Turing machine
zbMATH Keywords: Cauchy sequence representation
zbMATH Keywords: polynomial-time
author: Ker-I Ko
MaRDI profile type: Publication
full work available at URL: 0304-3975(84)90129-4
OpenAlex ID: W1994458535
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: Q3260573
cites work: A comparison of polynomial time reducibilities
cites work: The maximum value problem and NP real numbers
cites work: On the definitions of some complexity classes of real numbers
cites work: Computational complexity of real functions
cites work: On computable sequences
cites work: Recursive Real Numbers
cites work: Q5573961
cites work: Some observations on NP real numbers and P-selective sets
cites work: Recursion Theory and Dedekind Cuts
cites work: Nicht konstruktiv beweisbare Sätze der Analysis
description: scientific article; zbMATH DE number 3861147