André Nies (Auckland)

In 1975, Chaitin and Solovay studied sets of natural numbers
with minimal initial segment complexity. They looked at sets where the
prefixfree complexity of the first n bits is at most K(n), up to a constant.
In 2002, Downey, Hirschfeldt and Nies coined the term "Ktrivial" for such sets.
They came up with an easy "cost
function" construction of a computably enumerable, but incomputable
Ktrivial, and showed that Ktrivials are Turing incomplete.
This marks the beginning of an intense study of such sets. Nies, with some help by Hirschfeldt, showed that the Ktrivials 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 Ktrivial if and only if it cannot be cupped above the halting problem with an incomplete MartinLöf random set (Day and Miller 2011, relying on a result on nondensity of MartinLöf random sets in Π^{0}_{1} classes by Bienvenu Hoelzl, Miller and Nies 2011). Despite all these coincidences, major questions about the class of Ktrivials remain. We trace the developments of the past and discuss these open questions. 