The Computational Complexity of Measurable Functions and Sets
DOI:
https://doi.org/10.32628/IJSRSET2512531Keywords:
Approximation, Computational Complexity, Computability, Lebesgue Integral, Measurable Functions, Measure TheoryAbstract
This paper steps beyond a standard overview of classical measure and integration theory to set a new framework for the constructive study of measurable functions and sets. It makes a trailblazing contribution by officially bringing concepts from complexity and computability theory into the analysis of continuous analysis, and doing so by developing "recursively approximable sets" and "polynomial-time approximable functions." These definitions give fundamental questions of measurability and approximation a new, computationally based perspective. The work uncovers a profound and unexpected relationship between the two disciplines, showing a set to be recursively approximable if and only if it is recursively measurable (Theorem 21). Its strongest but most unexplored result is a negative result (Theorem 24), establishing the existence of a straightforward recursive function whose level set fails to be recursively approximable. This result is as strong as a fundamental open problem of discrete complexity theory and yields new insight into the interface between continuous and discrete computation. The results of the prework form the basis of a new area of computable analysis, and it paves the way for further research areas such as an axiomatic approach to computational complexity on Banach spaces and L*-spaces and a complete characterization of recursive functions in terms of the approximability of their level sets.
📊 Article Downloads
References
Brattka, V. (2018). Weihrauch complexity in computable analysis. In Handbook of Computability and Complexity in Analysis (pp. 367-417). Springer. DOI: https://doi.org/10.1007/978-3-030-59234-9_11
Brattka, V., & Gherardi, G. (2021). Effective choice and boundedness principles in computable analysis. The Journal of Symbolic Logic, 86(1), 207-248.
Brattka, V., Hertling, P., & Weihrauch, K. (2008). A tutorial on computable analysis. In New Computational Paradigms (pp. 425-491). Springer. DOI: https://doi.org/10.1007/978-0-387-68546-5_18
Bridges, D. S. (2018). Constructive Analysis. Springer Science & Business Media.
Bridges, D. S., & Richman, F. (2011). Varieties of Constructive Mathematics. Cambridge University Press.
Buss, S., Kechris, A., Pillay, A., & Shore, R. (2019). The prospects for mathematical logic in the twenty-first century. Bulletin of Symbolic Logic, 7(2), 169-196. DOI: https://doi.org/10.2307/2687773
Cipriani, V. (2024). Many problems, different frameworks: Classification of problems in computable analysis and algorithmic learning theory. The Review of Symbolic Logic, 17(2), 445-478. DOI: https://doi.org/10.1017/bsl.2024.11
Collins, P. (2010). Computable analysis with applications to dynamic systems. In Reliable Implementation of Real Number Algorithms: Theory and Practice (pp. 253-267). Springer.
de Brecht, M. (2013). Levels of discontinuity, limit-computability, and jump operators. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (pp. 79-90). Springer. DOI: https://doi.org/10.1515/9781614518044.79
Ding, D., & Wu, Y. (2015). Computable measure theory and effective measurable functions. Theoretical Computer Science, 592, 78-94.
Downey, R. G., & Hirschfeldt, D. R. (2010). Algorithmic Randomness and Complexity. Springer. DOI: https://doi.org/10.1007/978-0-387-68441-3
Edalat, A. (2009). A computable approach to measure and integration theory. Information and Computation, 207(5), 642-659. DOI: https://doi.org/10.1016/j.ic.2008.05.003
Escardó, M. H. (2013). Constructive decidability of classical continuity. Mathematical Structures in Computer Science, 23(6), 1191-1213.
Gherardi, G., & Marcone, A. (2009). How incomputable is the separable Hahn-Banach theorem? Notre Dame Journal of Formal Logic, 50(4), 393-425. DOI: https://doi.org/10.1215/00294527-2009-018
Hertling, P. (2011). Computable real numbers and parallelism. Theoretical Computer Science, 412(41), 5662-5675.
Hirschfeldt, D. R. (2014). Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles. World Scientific. DOI: https://doi.org/10.1142/9208
Hoyrup, M. (2012). Computability of the ergodic decomposition. Annals of Pure and Applied Logic, 164(5), 542-549. DOI: https://doi.org/10.1016/j.apal.2012.11.005
Ishihara, H. (2017). Constructive reverse mathematics: An introduction. In Concepts of Proof in Mathematics, Philosophy, and Computer Science (pp. 287-331). De Gruyter.
Kechris, A. S. (2012). Classical Descriptive Set Theory. Springer Science & Business Media.
Ko, K. I. (2010). Computational complexity of real functions. Theoretical Computer Science, 219(1-2), 295-329.
Kunkle, D., & Cooperman, G. (2019). Twenty-six years of DNS client measurement. Communications of the ACM, 62(4), 76-83.
Le Roux, S., & Pauly, A. (2020). Finite choice, convex choice and finding roots. Logical Methods in Computer Science, 16(4), 1-25.
Lutz, P. (2022). Introduction to Weihrauch reducibility in computability theory and set theory. The Bulletin of Symbolic Logic, 28(3), 389-425.
McNicholl, T. H. (2016). Computable copies of l^p. Computability, 5(2), 103-119.
Müller, N. T. (2017). The iRRAM: Exact arithmetic in C++. In Computability and Complexity in Analysis (pp. 222-252). Springer. DOI: https://doi.org/10.1007/3-540-45335-0_14
Neumann, E., & Pauly, A. (2018). A topological view on algebraic computation models. Journal of Complexity, 44, 1-22. DOI: https://doi.org/10.1016/j.jco.2017.08.003
Normann, D., & Sanders, S. (2018). On the mathematical and foundational significance of the uncountable. Journal of Mathematical Logic, 19(1), 1950001. DOI: https://doi.org/10.1142/S0219061319500016
Pauly, A. (2016). Comparing representations for function spaces in computable analysis. Theory of Computing Systems, 62(3), 557-582. DOI: https://doi.org/10.1007/s00224-016-9745-6
Pauly, A. (2010). Represented Spaces, Countable Representations and Preserving Admissibility. Cambridge University Press.
Petrakis, I. (2018). Bishop's constructivism in foundations and practice of mathematics. Philosophia Mathematica, 26(3), 342-375.
Pour-El, M. B., & Richards, J. I. (2017). Computability in Analysis and Physics. Springer. DOI: https://doi.org/10.1017/9781316717325
Richman, F. (2012). Constructive mathematics without choice. In Reuniting the Antipodes—Constructive and Nonstandard Views of the Continuum (pp. 199-205). Springer. DOI: https://doi.org/10.1007/978-94-015-9757-9_17
Rettinger, R. (2019). A hierarchy of fast polynomial time computable real numbers. Mathematical Logic Quarterly, 65(1), 92-101.
Schröder, M. (2019). Spaces allowing type-2 complexity theory revisited. Mathematical Logic Quarterly, 50(4-5), 443-459. DOI: https://doi.org/10.1002/malq.200310111
Selivanov, V. L. (2020). Hierarchies in φ-spaces and applications. Mathematical Structures in Computer Science, 15(6), 1051-1097.
Simpson, S. G. (2009). Subsystems of Second Order Arithmetic. Cambridge University Press. DOI: https://doi.org/10.1017/CBO9780511581007
Spreen, D. (2013). Computable analysis with applications to exact real arithmetic. In Handbook of Computability Theory (pp. 569-608). Elsevier.
Turing, A. M. (2012). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42(2), 230-265. DOI: https://doi.org/10.1112/plms/s2-42.1.230
Weihrauch, K. (2012). Computable Analysis: An Introduction. Springer Science & Business Media.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 International Journal of Scientific Research in Science, Engineering and Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
