1 The complexity of sets; 2 The descriptive complexity of strings; 3 Martin-Löf randomness and its variants; 4 Diagonally noncomputable functions; 5 Lowness properties and K-triviality; 6 Some advanced computability theory; 7 Randomness and betting strategies; 8 Classes of computational complexity; 9 Higher computability and randomness; Solutions to the exercises; References; Notation Index; Index
Summary
A monograph on the computational complexity and randomness of sets of natural numbers