Closed sets and operators thereon: representations, computability and complexity

DOI10.23638/LMCS-14(2:1)2018MaRDI QIDQ4637697zbMATH OpenFDO

Authors Carsten Rösnick-Neugebauer

Publication date 25 April 2018

Full work available at URL https://arxiv.org/abs/1701.00227

zbMATH Keywords

computable analysissecond-order representationtype-2 theory of effectivity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Theory of numerations, effectively presented structures (03D45) Computation over the reals, computable analysis (03D78)

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

Recommendations

• scientific article; zbMATH DE number 2013199
• scientific article; zbMATH DE number 1460545
• scientific article; zbMATH DE number 1101599
• Computability on subsets of Euclidean space. I: Closed and compact subsets
• scientific article; zbMATH DE number 3887669

Cited in

(17)

• Representations of the real numbers and of the open subsets of the set of real numbers
• Computability on subsets of Euclidean space. I: Closed and compact subsets
• Effectively closed sets and graphs of computable real functions.
• Parametrised second-order complexity theory with applications to the study of interval computation
• Computable operators on regular sets
• The computable multi-functions on multi-represented sets are closed under programming
• Singular coverings and non‐uniform notions of closed set computability
• Elementary computable topology
• scientific article; zbMATH DE number 17564 (Why is no real title available?)
• scientific article; zbMATH DE number 1538050 (Why is no real title available?)
• A simple and powerful approach for studying constructivity, computability, and complexity
• scientific article; zbMATH DE number 2163039 (Why is no real title available?)
• Computability and representations of the zero set
• Complexity of operators on compact sets
• Projection operators in the Weihrauch lattice
• Computable operators on co-regular subsets
• Computations with finite closure systems and implications

Describes a project that uses

Uses Software

• iRRAM

This page was built for publication: Closed sets and operators thereon: representations, computability and complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4637697)