Rösnick-Neugebauer, Carsten - Closed Sets and Operators thereon: Representations, Computability and Complexity

lmcs:4432 - Logical Methods in Computer Science, April 10, 2018, Volume 14, Issue 2
Closed Sets and Operators thereon: Representations, Computability and Complexity

Authors: Rösnick-Neugebauer, Carsten

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\"uller (2008), relating these problems to the P/UP/NP question in discrete complexity theory.

Source : oai:arXiv.org:1701.00227
DOI : 10.23638/LMCS-14(2:1)2018
Volume: Volume 14, Issue 2
Published on: April 10, 2018
Submitted on: January 3, 2017
Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,Mathematics - Logic,03D15,F.4.1


Consultation statistics

This page has been seen 83 times.
This article's PDF has been downloaded 63 times.