>[!abstract] >Meta-complexity refers to the complexity of computational problems and tasks that are themselves about computations and their complexity. For example, the Minimum Circuit Size Problem (given the truth table of a Boolean function $F$, compute the minimum circuit size of $F$) and the problem $K$poly of determining the polynomial-time bounded Kolmogorov complexity of a string are key meta-complexity problems. Meta-complexity provides a unifying framework for a variety of important tasks in several important areas of computer science, including computational complexity, proof complexity, cryptography, and learning theory ([[Simons Institute, 2025]]). >[!references] References >- [[Becker, 2024]] — A basic introduction to meta-complexity. >[!related] >- **North** (upstream): [[Complexity]] >- **West** (similar): — >- **East** (different): — >- **South** (downstream): [[Travelling salesman problem]]