Baire category and nowhere differentiability for feasible real functions

Mathematical Logic Quarterly 50 (45):460-472 (2004)


A notion of resource-bounded Baire category is developed for the class PC[0,1] of all polynomial-time computable real-valued functions on the unit interval. The meager subsets of PC[0,1] are characterized in terms of resource-bounded Banach-Mazur games. This characterization is used to prove that, in the sense of Baire category, almost every function in PC[0,1] is nowhere differentiable. This is a complexity-theoretic extension of the analogous classical result that Banach proved for the class C[0, 1] in 1931.

Download options


    Upload a copy of this work     Papers currently archived: 72,805

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

3 (#1,368,289)

6 months
1 (#386,031)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references

Citations of this work

Add more citations

Similar books and articles

Characterizations of Differentiability for H-Convex Functions in Stratified Groups.Valentino Magnani & Matteo Scienza - 2014 - Annali della Scuola Normale Superiore di Pisa- Classe di Scienze 13 (3):675-697.
Decomposing Baire Functions.J. Cichoń, M. Morayne, J. Pawlikowski & S. Solecki - 1991 - Journal of Symbolic Logic 56 (4):1273 - 1283.
An Analogue of the Baire Category Theorem.Philipp Hieronymi - 2013 - Journal of Symbolic Logic 78 (1):207-213.
Some Weak Forms of the Baire Category Theorem.Kyriakos Kermedis - 2003 - Mathematical Logic Quarterly 49 (4):369.
Some More Conservation Results on the Baire Category Theorem.Takeshi Yamazaki - 2000 - Mathematical Logic Quarterly 46 (1):105-110.
Counting as Integration in Feasible Analysis.Fernando Ferreira & Gilda Ferreira - 2006 - Mathematical Logic Quarterly 52 (3):315-320.
Effective Borel Measurability and Reducibility of Functions.Vasco Brattka - 2005 - Mathematical Logic Quarterly 51 (1):19-44.
Amoeba Reals.Haim Judah & Miroslav Repickẏ - 1995 - Journal of Symbolic Logic 60 (4):1168-1185.