Levin Complexity and Pseudodeterministic Constructions of Primes

I will discuss an influential notion of complexity for strings introduced by L. Levin, known as Kt complexity, and some recent related developments motivated by the task of explicitly constructing large primes.