Approximation to measurable functions and its relation to probabilistic computation

DOI10.1016/0168-0072(86)90005-9zbMath0613.03029OpenAlexW1969803220MaRDI QIDQ1088659

Ker-I. Ko

Publication date: 1986

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(86)90005-9

zbMATH Keywords

randomized algorithmscomputational complexity of real functionsLebesgue integralscomplexity of integrationcomputational complexity in measure theorypolynomial- time computable functionspolynomial-time approximable real functionspolynomial-time measurable setsrecursively measurable sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Constructive and recursive analysis (03F60) Recursive ordinals and ordinal notations (03F15)

Related Items (2)

In Memoriam: Ker-I Ko (1950–2018) ⋮ On the computational complexity of best Chebyshev approximations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Noncomputability in analysis and physics: A complete determination of the class of noncomputable linear operators
• The computational complexity of maximization and integration
• The maximum value problem and NP real numbers
• Computational complexity of real functions
• Recursive function theory and numerical analysis
• On computable sequences
• On the definitions of computable real continuous functions
• On the definitions of some complexity classes of real numbers
• Computability and Noncomputability in Classical Analysis
• The Complexity of Enumeration and Reliability Problems
• A computable ordinary differential equation which possesses no computable solution
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• On a simple definition of computable function of a real variable‐with applications to functions of a complex variable
• A Fast Monte-Carlo Test for Primality
• On the Definition of Computable Function of a Real Variable
• Computational Complexity of Probabilistic Turing Machines
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Nicht konstruktiv beweisbare Sätze der Analysis
• [Russian Text Ignored]

This page was built for publication: Approximation to measurable functions and its relation to probabilistic computation