André Nies (Auckland)
Ten Years of Triviality

In 1975, Chaitin and Solovay studied sets of natural numbers with minimal initial segment complexity. They looked at sets where the prefix-free complexity of the first n bits is at most K(n), up to a constant. In 2002, Downey, Hirschfeldt and Nies coined the term "K-trivial" for such sets. They came up with an easy "cost function" construction of a computably enumerable, but incomputable K-trivial, and showed that K-trivials are Turing incomplete.

This marks the beginning of an intense study of such sets. Nies, with some help by Hirschfeldt, showed that the K-trivials coincide with the low for random sets in the sense of Kucera and Terwijn. More coincidences followed, the most recent being that a set is K-trivial if and only if it cannot be cupped above the halting problem with an incomplete Martin-Löf random set (Day and Miller 2011, relying on a result on non-density of Martin-Löf random sets in Π01 classes by Bienvenu Hoelzl, Miller and Nies 2011). Despite all these coincidences, major questions about the class of K-trivials remain.

We trace the developments of the past and discuss these open questions.