André Nies: Structure within the class of K-trivial sets


Title: Structure within the class of K-trivial sets

Prof. André Nies
Department of Computer Science
University of Auckland
Date:    6 February 2017 (Monday)
Time:      4.00pm – 5.00pm
Venue:     MAS Executive Classroom 1 #03-06,
School of Physical and Mathematical Sciences  and quantum settings

The K-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity K grows as slowly as possible. Since 2002, many  alternative characterisations of this class have been found: properties such as low for K, low for Martin-Löf (ML) randomness, and basis for ML randomness, which state in one way or the other that the set is close to computable.

Initially the class looked quite amorphous. More recently, internal structure has been found. Bienvenu et al. (JEMS 2016) showed that there is a “smart” K-trivial set, in the sense that any random oracle computing it computes all K-trivials. Greenberg, Miller and Nies(submitted)  showed that there is a dense hierarchy of subclasses. Even more recent results with Turetsky combine the two approaches using cost functions. ML-reducibility (A is below B if every random oracle computing B also computes A) appears to a good way to compare the complexity of K-trivials, but the vexing question remains whether this reducibility is arithmetical.


Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.