Martin Ziegler, Quantitative Coding and Complexity Theory of Continuous Data

Specifying a computational problem requires fixing encodings for input and output: encoding graphs as adjacency matrices, characters as integers, integers as bit strings, and vice versa. For such discrete data, the actual encoding is usually straightforward and/or complexity-theoretically inessential (up to polynomial time, say).

But concerning continuous data, already real numbers naturally suggest various encodings with very different computational properties.

We recall the existing qualitative theory of computably ‘sensible’ encodings of topological spaces; and we newly develop the quantitative theory of complexity-theoretically ‘sensible’ encodings of metric spaces.

Joint work with Donghyun Lim.