| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Higher-order complexity in analysis
Abstract : We present ongoing work on the development of complexity theory in analysis. Kawamura and Cook recently showed how to carry out complexity theory on the space C[0,1] of continuous real functions on the unit interval. It is done, as in computable analysis, by representing objects by first-order functions (from finite words to finite words, say) and by measuring the complexity of a second-order functional in terms of second-order polynomials. We prove that this framework cannot be directly applied to spaces that are not $\sigma$-compact. However, representing objects by higher-order functions (over finite words, say) makes it possible to carry out complexity theory on such spaces: for this purpose we develop the complexity of higher-order functionals. At orders above 3, our class of polynomial-time computable functionals strictly contains the class BFF of Buss, Cook and Urquhart.
Cited literature [23 references]
https://hal.inria.fr/hal-00915973
Contributor : Mathieu Hoyrup Connect in order to contact the contributor
Submitted on : Monday, December 9, 2013 - 3:27:37 PM
Last modification on : Saturday, October 16, 2021 - 11:26:05 AM
Long-term archiving on: : Sunday, March 9, 2014 - 11:50:23 PM
Contributor : Mathieu Hoyrup Connect in order to contact the contributor
Submitted on : Monday, December 9, 2013 - 3:27:37 PM
Last modification on : Saturday, October 16, 2021 - 11:26:05 AM
Long-term archiving on: : Sunday, March 9, 2014 - 11:50:23 PM
File
final.pdf
Files produced by the author(s)