Skip to main content

Analytical properties of resource-bounded real functionals

Férée, Hugo, Gomaa, Walid, Hoyrup, Mathieu (2014) Analytical properties of resource-bounded real functionals. Journal of Complexity, 30 (5). pp. 647-671. ISSN 0885-064X. E-ISSN 1090-2708. (doi:10.1016/j.jco.2014.02.008) (KAR id:64714)

Abstract

Computable analysis is an extension of classical discrete computability by enhancing the normal Turing machine model. It investigates mathematical analysis from the computability perspective. Though it is well developed on the computability level, it is still under developed on the complexity perspective, that is, when bounding the available computational resources. Recently Kawamura and Cook developed a framework to define the computational complexity of operators arising in analysis. Our goal is to understand the effects of complexity restrictions on the analytical properties of the operator. We focus on the case of norms over C[0,1] and introduce the notion of dependence of a norm on a point and relate it to the query complexity of the norm. We show that the dependence of almost every point is of the order of the query complexity of the norm. A norm with small complexity depends on a few points but, as compensation, highly depends on them. We briefly show how to obtain similar results for non-deterministic time complexity. We characterize the functionals that are computable using one oracle call only and discuss the uniformity of that characterization. This paper is a significant revision and expansion of an earlier conference version.

Item Type: Article
DOI/Identification number: 10.1016/j.jco.2014.02.008
Uncontrolled keywords: Computable analysis, computational complexity, oracle Turing machine, polynomial time computable functional, norm, non-deterministic complexity
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Hugo Feree
Date Deposited: 24 Nov 2017 16:10 UTC
Last Modified: 16 Feb 2021 13:50 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/64714 (The current URI for this page, for reference purposes)

University of Kent Author Information

Férée, Hugo.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.