×

zbMATH — the first resource for mathematics

Parametrised second-order complexity theory with applications to the study of interval computation. (English) Zbl 1454.03057
Summary: We extend the framework for complexity of operators in analysis devised by A. Kawamura and S. Cook [ACM Trans. Comput. Theory 4, No. 2, Article No. 5, 24 p. (2012; Zbl 1322.68083)] to allow for the treatment of a wider class of representations. The main novelty is to endow represented spaces of interest with an additional function on names, called a parameter, which measures the complexity of a given name. This parameter generalises the size function which is usually used in second-order complexity theory and therefore also central to the framework of Kawamura and Cook. The complexity of an algorithm is measured in terms of its running time as a second-order function in the parameter, as well as in terms of how much it increases the complexity of a given name, as measured by the parameters on the input and output side.
As an application we develop a rigorous computational complexity theory for interval computation. In the framework of Kawamura and Cook the representation of real numbers based on nested interval enclosures does not yield a reasonable complexity theory. In our new framework this representation is polytime equivalent to the usual Cauchy representation based on dyadic rational approximation. By contrast, the representation of continuous real functions based on interval enclosures is strictly smaller in the polytime reducibility lattice than the usual representation, which encodes a modulus of continuity. Furthermore, the function space representation based on interval enclosures is optimal in the sense that it contains the minimal amount of information amongst those representations which render evaluation polytime computable.
MSC:
03D78 Computation over the reals, computable analysis
03D65 Higher-type and set recursion theory
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Software:
Ariadne; iRRAM
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Benvenuti, Luca; Bresolin, Davide; Casagrande, Alberto; Collins, Pieter; Ferrari, Alberto; Mazzi, Emanuele; Sangiovanni-Vincentelli, Alberto; Villa, Tiziano, Reachability computation for hybrid systems with Ariadne, IFAC Proc. Vol., 41, 2, 8960-8965 (2008), 17th IFAC World Congress
[2] Blum, Lenore; Cucker, Felipe; Shub, Michael; Smale, Steve, Complexity and Real Computation (1998), Springer · Zbl 0872.68036
[3] Brauße, Franz; Steinberg, Florian, A minimal representation for continuous functions (2017), preprint
[4] Blum, Lenore; Shub, Mike; Smale, Steve, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Am. Math. Soc., 21, 1, 1-46 (1989) · Zbl 0681.03020
[5] Cook, Stephen A., Computability and complexity of higher type functions, (Moschovakis, Yiannis N., Logic From Computer Science: Proceedings of a Workshop Held. Logic From Computer Science: Proceedings of a Workshop Held, November 13-17, 1989 (1992), Springer: Springer New York, NY), 51-72 · Zbl 0757.03021
[6] Férée, Hugo; Gomaa, Walid; Hoyrup, Mathieu, Analytical properties of resource-bounded real functionals, J. Complex., 30, 5, 647-671 (2014) · Zbl 1401.03084
[7] Férée, Hugo; Hoyrup, Mathieu, Higher order complexity in analysis (2013), preprint, extended abstract presented at CCA conference 2013 · Zbl 1366.03218
[8] Friedman, Harvey, On the computational complexity of maximization and integration, Adv. Math., 53, 80-98 (1984) · Zbl 0563.03023
[9] Férée, Hugo; Ziegler, Martin, On the computational complexity of positive linear functionals on C[0;1], (MACIS Conference (2015)) · Zbl 06585050
[10] Grzegorczyk, Andrzej, Computable functionals, Fundam. Math., 42, 168-202 (1955) · Zbl 0066.26001
[11] Grzegorczyk, Andrzej, On the definition of computable functionals, Fundam. Math., 42, 232-239 (1955) · Zbl 0067.00301
[12] Grzegorczyk, Andrzej, On the definitions of computable real continuous functions, Fundam. Math., 44, 1, 61-71 (1957) · Zbl 0079.24801
[13] Irwin, Robert J.; Royer, James S.; Kapron, Bruce M., On characterizations of the basic feasible functionals, part I, J. Funct. Program., 11, 1, 117-153 (2001) · Zbl 0992.68020
[14] Kawamura, Akitoshi, Lipschitz continuous ordinary differential equations are polynomial-space complete, Comput. Complex., 19, 2, 305-332 (2010) · Zbl 1232.03031
[15] Kapron, Bruce M.; Cook, Stephen A., A new characterization of type-2 feasibility, SIAM J. Comput., 25, 1, 117-132 (1996) · Zbl 0843.68028
[16] Kawamura, Akitoshi; Cook, Stephen, Complexity theory for operators in analysis, ACM Trans. Comput. Theory, 4, 2, 1-24 (May 2012)
[17] Ko, Ker-I.; Friedman, Harvey, Computational complexity of real functions, Theor. Comput. Sci., 20, 323-352 (1982) · Zbl 0498.03047
[18] Kawamura, Akitoshi; Müller, Norbert Th.; Rösnick, Carsten; Ziegler, Martin, Parameterized uniform complexity in numerics: from smooth to analytic, from NP-hard to polytime, CoRR (2012)
[19] Kawamura, Akitoshi; Müller, Norbert; Rösnick, Carsten; Ziegler, Martin, Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevre’s hierarchy, J. Complex., 31, 5, 689-714 (2015) · Zbl 1336.68133
[20] Ko, Ker-I., On the computational complexity of ordinary differential equations, Inf. Control, 58, 157-194 (1983) · Zbl 0541.03035
[21] Ko, Ker-I., Complexity Theory of Real Functions, Progress in Theoretical Computer Science. (1991), Birkhäuser Boston, Inc.: Birkhäuser Boston, Inc. Boston, MA · Zbl 0791.03019
[22] Kawamura, Akitoshi; Ota, Hiroyuki, Small complexity classes for computable analysis, (Mathematical Foundations of Computer Science 2014. Part II. Mathematical Foundations of Computer Science 2014. Part II, Lecture Notes in Comput. Sci., vol. 8635 (2014), Springer: Springer Heidelberg), 432-444 · Zbl 1427.68097
[23] Konečný, Michal, A Haskell library for approximating exact real numbers (AERN) (November 2017), retrieved 6th, 16:00
[24] Kawamura, Akitoshi; Pauly, Arno, Function spaces for second-order polynomial time, (Language, Life, Limits. Language, Life, Limits, Lecture Notes in Comput. Sci., vol. 8493 (2014), Springer: Springer Cham), 245-254 · Zbl 1433.03122
[25] Kawamura, Akitoshi; Pauly, Arno, On function spaces and polynomial-time computability, CoRR (2014) · Zbl 1433.03122
[26] Kawamura, Akitoshi; Steinberg, Florian, Polynomial running times for polynomial-time oracle machines, (Dale, Miller, 2nd International Conference on Formal Structures for Computation and Deduction (FSCD 2017). 2nd International Conference on Formal Structures for Computation and Deduction (FSCD 2017), Leibniz International Proceedings in Informatics (LIPIcs), vol. 84 (2017), Dagstuhl: Dagstuhl Germany), 1-18, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
[27] Kawamura, Akitoshi; Steinberg, Florian; Thies, Holger, Parameterized complexity for uniform operators on multidimensional analytic functions and ODE solving, (Logic, Language, Information, and Computation - 25th International Workshop. Logic, Language, Information, and Computation - 25th International Workshop, WoLLIC 2018, Bogota, Colombia, July 24-27, 2018, Proceedings (2018)), 223-236 · Zbl 06958315
[28] Kawamura, Akitoshi; Thies, Holger; Ziegler, Martin, Average-case polynomial-time computability of Hamiltonian dynamics, (43rd International Symposium on Mathematical Foundations of Computer Science. 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK (2018)), 1-17
[29] Kreitz, Christoph; Weihrauch, Klaus, Theory of representations, Theor. Comput. Sci., 38, 35-53 (1985) · Zbl 0588.03031
[30] Lacombe, Daniel, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles. II, III, C. R. Acad. Sci. Paris, 241, 13-14, 151-153 (1955) · Zbl 0066.26101
[31] Lambov, Branimir, Complexity and Intensionality in a Type-1 Framework for Computable Analysis, 442-461 (2005), Springer: Springer Berlin Heidelberg · Zbl 1136.03325
[32] Lambov, Branimir, The basic feasible functionals in computable analysis, J. Complex., 22, 6, 909-917 (2006) · Zbl 1113.03056
[33] Mehlhorn, Kurt, Polynomial and abstract subrecursive classes, J. Comput. Syst. Sci., 12, 2, 147-178 (1976), Sixth Annual ACM Symposium on the Theory of Computing (Seattle, Wash., 1974) · Zbl 0329.68049
[34] Müller, Norbert Th., iRRAM - exact arithmetic in C++ (2019) · Zbl 0985.65523
[35] Müller, Norbert Th., The iRRAM: exact arithmetic in C++, (Blanck, Jens; Brattka, Vasco; Hertling, Peter, Computability and Complexity in Analysis: 4th International Workshop. Computability and Complexity in Analysis: 4th International Workshop, CCA 2000 Swansea, UK, September 17-19, 2000. Computability and Complexity in Analysis: 4th International Workshop. Computability and Complexity in Analysis: 4th International Workshop, CCA 2000 Swansea, UK, September 17-19, 2000, Selected Papers (2001), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 222-252 · Zbl 0985.65523
[36] Pezzoli, Elena, On the computational complexity of type 2 functionals, (Nielsen, Mogens; Thomas, Wolfgang, Computer Science Logic: 11th International Workshop, CSL ’97 Annual Conference of the EACSL Aarhus. Computer Science Logic: 11th International Workshop, CSL ’97 Annual Conference of the EACSL Aarhus, Denmark, August 23-29, 1997. Computer Science Logic: 11th International Workshop, CSL ’97 Annual Conference of the EACSL Aarhus. Computer Science Logic: 11th International Workshop, CSL ’97 Annual Conference of the EACSL Aarhus, Denmark, August 23-29, 1997, Selected Papers (1998), Springer: Springer Berlin Heidelberg, Berlin, Heidelberg) · Zbl 0910.03027
[37] Pouly, Amaury; Graça, Daniel S., Computational complexity of solving polynomial differential equations over unbounded domains, Theor. Comput. Sci., 626, 67-82 (2016) · Zbl 1416.65197
[38] Rettinger, Robert, Computational complexity in analysis, (CCA (2013))
[39] Schröder, Matthias, Admissible Representations for Continuous Computations (2002), FernUniversität Hagen, PhD thesis · Zbl 1020.18005
[40] Schröder, Matthias, Extended admissibility, Theor. Comput. Sci., 284, 2, 519-538 (2002), Computability and complexity in analysis (Castle Dagstuhl, 1999) · Zbl 1042.68050
[41] Schröder, Matthias, Spaces allowing type-2 complexity theory revisited, Math. Log. Q., 50, 4-5, 443-459 (2004) · Zbl 1058.03069
[42] Schröder, Matthias; Steinberg, Florian, Bounded time computation on metric spaces and Banach spaces, (2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (2017)), 1-12
[43] Steinberg, Florian, Computational Complexity Theory for Advanced Function Spaces in Analysis (2016), Technische Universität Darmstadt, PhD thesis · Zbl 06617641
[44] Steinberg, Florian, Complexity theory for spaces of integrable functions, Log. Methods Comput. Sci., 13, 3 (Sep 2017)
[45] Turing, Alan M., On computable numbers, with an application to the entscheidungsproblem, Proc. Lond. Math. Soc., s2-42, 1, 230-265 (1937), 01 · JFM 62.1059.03
[46] Weihrauch, Klaus, Computable Analysis, Texts in Theoretical Computer ScienceAn EATCS Series (2000), Springer-Verlag: Springer-Verlag Berlin · Zbl 0956.68056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.