Closed Sets and Operators thereon: Representations, Computability and Complexity

摘要

The TTE approach to Computable Analysis is the study of so-calledrepresentations (encodings for continuous objects such as reals, functions, andsets) with respect to the notions of computability they induce. A rich varietyof such representations had been devised over the past decades, particularlyregarding closed subsets of Euclidean space plus subclasses thereof (likecompact subsets). In addition, they had been compared and classified withrespect to both non-uniform computability of single sets and uniformcomputability of operators on sets. In this paper we refine theseinvestigations from the point of view of computational complexity. Benefitingfrom the concept of second-order representations and complexity recentlydevised by Kawamura & Cook (2012), we determine parameterized complexity boundsfor operators such as union, intersection, projection, and more generallyfunction image and inversion. By indicating natural parameters in addition tothe output precision, we get a uniform view on results by Ko (1991-2013),Braverman (2004/05) and Zhao & M"uller (2008), relating these problems to theP/UP/NP question in discrete complexity theory.