Title: Closed Sets and Operators thereon: Representations, Computability and Complexity,
Abstract: The TTE approach to Computable Analysis is the study of so-called
representations (encodings for continuous objects such as reals, functions, and
sets) with respect to the notions of computability they induce. A rich variety
of such representations had been devised over the past decades, particularly
regarding closed subsets of Euclidean space plus subclasses thereof (like
compact subsets). In addition, they had been compared and classified with
respect to both non-uniform computability of single sets and uniform
computability of operators on sets. In this paper we refine these
investigations from the point of view of computational complexity. Benefiting
from the concept of second-order representations and complexity recently
devised by Kawamura & Cook (2012), we determine parameterized complexity bounds
for operators such as union, intersection, projection, and more generally
function image and inversion. By indicating natural parameters in addition to
the output precision, we get a uniform view on results by Ko (1991-2013),
Braverman (2004/05) and Zhao & Müller (2008), relating these problems to the
P/UP/NP question in discrete complexity theory.