Annals of Pure and Applied Logic 30 (2):173-200 (1986)

A theory of approximation to measurable sets and measurable functions based on the concepts of recursion theory and discrete complexity theory is developed. The approximation method uses a model of oracle Turing machines, and so the computational complexity may be defined in a natural way. This complexity measure may be viewed as a formulation of the average-case complexity of real functions—in contrast to the more restrictive worst-case complexity. The relationship between these two complexity measures is further studied and compared with the notion of the distribution-free probabilistic computation. The computational complexity of the Lebesgue integral of polynomial-time approximable functions is studied and related to the question “FP = ♯P?”
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(86)90005-9
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,548
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Nicht Konstruktiv Beweisbare Sätze der Analysis.Ernst Specker - 1949 - Journal of Symbolic Logic 14 (3):145-158.
On the Definition of Computable Function of a Real Variable.J. C. Shepherdson - 1976 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 22 (1):391-402.
On the Definition of Computable Function of a Real Variable.J. C. Shepherdson - 1976 - Mathematical Logic Quarterly 22 (1):391-402.

View all 12 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Measurable Chromatic Numbers.Benjamin D. Miller - 2008 - Journal of Symbolic Logic 73 (4):1139-1157.
Computability of Measurable Sets Via Effective Topologies.Yongcheng Wu & Decheng Ding - 2005 - Archive for Mathematical Logic 45 (3):365-379.
Towards an Expanded Epistemology for Approximations.Jeffry L. Ramsey - 1992 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1992:154 - 164.
Authentic Intentionality.John Haugeland - 2002 - In Matthias Scheutz (ed.), Computationalism: New Directions. MIT Press.
No Borel Connections for the Unsplitting Relations.Heike Mildenberger - 2002 - Mathematical Logic Quarterly 48 (4):517-521.
On the Revision of Probabilistic Belief States.Craig Boutilier - 1995 - Notre Dame Journal of Formal Logic 36 (1):158-183.
Effective Borel Measurability and Reducibility of Functions.Vasco Brattka - 2005 - Mathematical Logic Quarterly 51 (1):19-44.
Probabilistic Grammars and Languages.András Kornai - 2011 - Journal of Logic, Language and Information 20 (3):317-328.


Added to PP index

Total views
12 ( #728,814 of 2,348,443 )

Recent downloads (6 months)
1 ( #511,012 of 2,348,443 )

How can I increase my downloads?


My notes