The circuit complexity of a Boolean function is defined to be the size of a minimum circuit that computes the function. What is the computational complexity (so called "meta-complexity") of computing the circuit complexity? This question dates back to at least as early as 1970s, when Cook and Levin introduced the theory of NP-completeness. Although Levin proved NP-completeness of computing the DNF formula complexity of partial functions, whether it can be extended to circuit complexity has been open, until recently.

In this talk, we prove NP-completeness of MCSP*, the problem of computing the circuit complexity of partial functions. More broadly, we present an emerging paradigm of meta-complexity, which suggests that studying meta-complexity would lead to the resolution of worst-case versus average-case complexities of NP.

The talk is based on https://eccc.weizmann.ac.il/report/2022/119/ and http://bulletin.eatcs.org/index.php/beatcs/article/view/688.