Paper Info
Title
Complexity Theory of (Functions on) Compact Metric Spaces.
Abstract
We promote the theory of computational complexity on metric spaces: as natural common generalization of (i) the classical discrete setting of integers, binary strings, graphs etc. as well as of (ii) the bit-complexity theory on real numbers and functions according to Friedman, Ko (1982ff), Cook, Braverman et al.; as (iii) resource-bounded refinement of the theories of computability on, and representations of, continuous universes by Pour-El&Richards (1989) and Weihrauch (1993ff); and as (iv) computational perspective on quantitative concepts from classical Analysis: Our main results relate (i.e. upper and lower bound) Kolmogorov's entropy of a compact metric space X polynomially to the uniform relativized complexity of approximating various families of continuous functions on X. The upper bounds are attained by carefully crafted oracles and bit-cost analyses of algorithms perusing them. They all employ the same representation (i.e. encoding, as infinite binary sequences, of the elements) of such spaces, which thus may be of own interest. The lower bounds adapt adversary arguments from unit-cost Information-Based Complexity to the bit model. They extend to, and indicate perhaps surprising limitations even of, encodings via binary string functions (rather than sequences) as introduced by Kawamura&Cook (SToC'2010, §3.4). These insights offer some guidance towards suitable notions of complexity for higher types.
Year
DOI
Venue
2016
10.1145/2933575.2935311
LICS
Keywords
Field
DocType
Recursive Analysis, Bit Complexity, Metric Entropy
Integer,Discrete mathematics,Continuous function,Combinatorics,Upper and lower bounds,Computability,Compact space,Metric space,Real number,Mathematics,Computational complexity theory
Conference
ISSN
ISBN
Citations 
1043-6871
978-1-4503-4391-6
2
PageRank 
References 
Authors
0.42
31
3
Name
Order
Citations
PageRank
Akitoshi Kawamura110215.84
Florian Steinberg251.84
Martin Ziegler320.76