Premium
Baire category and nowhere differentiability for feasible real functions
Author(s) -
Breutzmann Josef M.,
Juedes David W.,
Lutz Jack H.
Publication year - 2004
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200310112
Subject(s) - mathematics , baire space , differentiable function , baire category theorem , bounded function , unit interval , class (philosophy) , baire measure , banach space , discrete mathematics , extension (predicate logic) , pure mathematics , mathematical analysis , artificial intelligence , computer science , programming language
A notion of resource‐bounded Baire category is developed for the class P C [0,1] of all polynomial‐time computable real‐valued functions on the unit interval. The meager subsets of P C [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 P C [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. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)