From the logicians I learned about K-trivial sets. Let K(x) be the prefix-free Kolmogorov complexity of x, i.e., the size of the smallest program that generates x. There are several equivalent definitions of K-trivial sets, here is two of them. A are K-trivial if
- For some constant c, for all x, K(x) ≤ KA(x)+c, where KA(x) is the smallest program generating x with access to oracle A.
- For some constant c, for all n, K(A1:n) ≤ K(n)+c, where A1:n are the first n bits of the characteristic sequence of A.
- All computable sets are K-trivial and there are K-trivial sets that are not computable.
- There are only a countable number of K-trivial sets. In fact there are only a finite number of K-trivial sets for each fixed constant c above.
- Every K-trivial set is super-low, that is the halting problem relative to a K-trivial set is non-adaptively reducible to the halting problem.
- Every K-trivial non-adaptively reduces to a computably-enumerable set.
- Every set reducible to a K-trivial is K-trivial.
- The disjoint union of two K-trivial sets is K-trivial.
- Random sets are still random relative to A.
More about K-trivial sets and everything else computably random in a great book by Downey and Hirschfeldt.
Us complexity theorists started thinking about polynomial-time versions of K-trivial sets but probably won't have as many nice properties.