一句话：在TTE框架下用二阶表示与参数化复杂度统一刻画闭集上并、交、投影、像与求逆等算子的复杂度。
本文在TTE（Type Two Effectivity）可计算分析框架下研究闭集及其上算子的复杂度。TTE通过表示（representation）刻画实数、函数、集合等连续对象的可计算性；已有多种针对欧氏空间闭集及其子类（如紧集）的表示，并按单集非一致性可计算性与算子的均匀可计算性进行比较分类。作者引入Kawamura & Cook（2012）的二阶表示与复杂度概念，对并、交、投影以及更一般的函数像与求逆等算子给出参数化复杂度界。通过在输出精度之外指出自然参数，文章统一了Ko（1991-2013）、Braverman（2004/05）和Zhao & Müller（2008）的结果，并将其与离散复杂度中的P/UP/NP问题联系起来。
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.
@article{paperbot414,
title = {Closed Sets and Operators thereon: Representations, Computability and Complexity},
author = {Carsten Rösnick-Neugebauer},
journal = {Logical Methods in Computer Science},
volume = {Volume 14, Issue 2},
year = {2018},
doi = {10.23638/lmcs-14(2:1)2018}
}