Title: Discovering structure within the class of K-trivial sets
by Andre Nies (University of Auckland) as part of Computability theory and applications

Abstract
Joint work with Noam Greenberg, Joseph Miller, and Dan Turetsky

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. Chaitin introduced this notion in about 1975, and showed that each K-trivial is Turing below the halting set. Shortly after, Solovay proved that a K-trivial set can be noncomputable.

In the past two decades, many alternative characterisations of this class have been found: properties such as  being low for K, low for Martin-Löf (ML) randomness, and a basis for  ML randomness, which state in one way or the other that the set is close to computable. 

Initially, the class of noncomputable K-trivials appeared to be amorphous. More recently, evidence of an internal structure has been found. Most of these results can be phrased in the language of a mysterious reducibility on the K-trivials which is weaker than Turing’s: A is ML-below B if each ML-random computing B also computes A.

Bienvenu, Greenberg, Kucera, Nies and Turetsky (JEMS 2016) showed that there an ML complete K-trivial set. Greenberg, Miller and Nies  (JML, 2019) established a dense hierarchy of subclasses of the K-trivials based on fragments of Omega computing the set, and each such subclass is an initial segment for ML. More recent results generalise these approaches using cost functions. They also show that each K-trivial set is ML-equivalent to a c.e. K-trivial.

The extreme lowness of K-trivials, far from being an obstacle, allows for methods which don’t work in a wider setting. The talk provides an overview and discusses open questions. For instance, is ML-completeness an arithmetical property of K-trivials?