Mathematics of the impossible: Computational Complexity, Chapter 3: The grand challenge
Thoughts 2023-02-02
Summary:
All posts in this series. A PDF version of this post will be published with a delay, but if you’d like to have it soon let me know. Contents 1 The grand challenge 1.1 Information bottleneck: Palindromes requires quadratic time on TMs 1.2 Counting: impossibility results for non-explicit functions 1.3 Diagonalization: Enumerating machines 1.3.1 1.4 […]