In this talk I'll explain some work in theoretical computer science, done in the second half of the 20th century, which led to further understanding, more connections and basic problems about these notions. These developments include the immense power of probabilistic proofs, the surprising weakness of computational randomness, the P versus NP problem and its meaning for science and human knowledge. Key to these developments is Computational Complexity - the field exploring the difficulty of computational problems.
The talk is designed for scientists of all disciplines.