André Nies (Auckland)
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.