Approximation to measurable functions and its relation to probabilistic computation
type: Item
instance of: scholarly article
title: Approximation to measurable functions and its relation to probabilistic computation
zbMATH Open document ID: 0613.03029
DOI: 10.1016/0168-0072(86)90005-9
published in: Annals of Pure and Applied Logic
publication date: 1986-01-01T00:00:00Z
review text: This paper is one of a sequence of papers by the author and H. Friedman on computational complexity of real functions. The basic notion of computational complexity of continuous real functions is developed by the author and \textit{H. Friedman} [Theor. Comput. Sci. 20, 323-352 (1982; Zbl 0498.03047)]. The paper under review deals with computational complexity in measure theory and complexity of integration. It first extends the notion of recursively measurable sets, as defined by \textit{G. Kreisel} and \textit{D. Lacombe} [C. R. Acad. Sci., Paris 245, 1106-1109 (1957; Zbl 0079.009)] and \textit{N. A. Shanin} [Tr. Mat. Inst. Steklova 67, 15-294 (1962; Zbl 0113.008)], to define the class of polynomial-time approximable (or, polynomial-time measurable) sets and polynomial-time approximable real functions. One of the main results shows an interesting relationship between polynomial-time approximability and randomized algorithms which have been developed in the context of the NP-completeness theory. It is shown that the Lebesgue integrals of polynomial-time approximable functions are always polynomial-time computable if and only if \(FP=\#P\). This is a generalization of \textit{H. Friedman}'s [Adv. Math. 53, 80-98 (1984; Zbl 0563.03023)] result on the computational complexity of the Riemann integration of polynomial-time computable functions.
Mathematics Subject Classification ID: 03F60
Mathematics Subject Classification ID: 03F15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3991499
zbMATH Keywords: polynomial-time measurable sets
zbMATH Keywords: computational complexity of real functions
zbMATH Keywords: computational complexity in measure theory
zbMATH Keywords: complexity of integration
zbMATH Keywords: recursively measurable sets
zbMATH Keywords: polynomial-time approximable real functions
zbMATH Keywords: randomized algorithms
zbMATH Keywords: Lebesgue integrals
zbMATH Keywords: polynomial- time computable functions
author: Ker-I Ko
MaRDI profile type: Publication
full work available at URL: 0168-0072(86)90005-9
OpenAlex ID: W1969803220
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: A Machine-Independent Theory of the Complexity of Recursive Functions
cites work: The computational complexity of maximization and integration
cites work: Q4198056
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: On the definitions of computable real continuous functions
cites work: Q3260573
cites work: Q5592246
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: Q3246326
cites work: Q3966120
cites work: Q3227567
cites work: Q3243267
cites work: Recursive function theory and numerical analysis
cites work: On computable sequences
cites work: Q3261421
cites work: On a simple definition of computable function of a real variable‐with applications to functions of a complex variable
cites work: A computable ordinary differential equation which possesses no computable solution
cites work: Computability and Noncomputability in Classical Analysis
cites work: Noncomputability in analysis and physics: A complete determination of the class of noncomputable linear operators
cites work: Q4164569
cites work: Q5573961
cites work: Q5526189
cites work: [Russian Text Ignored]
cites work: Q5556429
cites work: On the Definition of Computable Function of a Real Variable
cites work: A Fast Monte-Carlo Test for Primality
cites work: Nicht konstruktiv beweisbare Sätze der Analysis
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
description: scientific article; zbMATH DE number 3991499