기초과학연구원 이산수학그룹
On February 16, 2021, Martin Ziegler from KAIST gave a talk at the Discrete Math Seminar on the encoding problem of metric spaces from the perspective of the complexity theory. The title of his talk was “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.