How hard is it to prove that problems are hard to solve? Meta-complexity theorists have been asking questions like this for decades. A string of recent results has started to deliver answers.
Complexity theorists are confronting their most puzzling problem yet: complexity theory itself.
August 17, 2023