We show that several meta-complexity problems are NP-hard under randomized polynomial-time (half-Levin) reductions, and provably cannot be NP-hard under randomized Levin reductions, under the assumptions that
(cryptography): there exists a subexponentially-secure indistinguishability obfuscator in the sense of Barak et al. (JACM 2012), and
(proof complexity): there are no infinitely-often subexponentially-optimal propositional proof systems in the sense of Cook and Reckhow (J. Symb. Log. 1979) and Krajicek and Pudlak (J. Symb. Log. 1989).
In particular, this is shown for
(1) the problem of improper full-support PAC learning of boolean functions in P/poly, and
(2) a gap-version of the Implicit Minimum Circuit Size Problem (ImpMCSP).
More precisely, for item (1), we consider the following learning problem $TotL$: Given a circuit sampling a distribution $\mathcal{E}$ of labeled examples $(x, b)\in\{0,1\}^n\times\{0,1\}$ so that every $x\in\{0,1\}^n$ is in the support of $\mathcal{E}$, distinguish between the two cases: (a) there exists a circuit $C$ of size at most $s$ that, for all $(x,b)$ in the support of $\mathcal{E}$, $C(x)=b$, and (b) no circuit $C$ of size $subexp(s)$ satisfies $C(x)=b$ with probability noticeably higher than $1/2$ over samples $(x,b)$ from $\mathcal{E}$.
Gap-ImpMCSP in item (2) is defined as follows. Given a circuit $C$ sampling a distribution $\mathcal{E}$ of labeled examples $(x,f(x))\in\{0,1\}^n\times\{0,1\}$ for some boolean function $f$ so that every $x\in\{0,1\}^n$ is in the support of $\mathcal{E}$, distinguish between the two cases: (a) the circuit complexity of $f$ is at most $s$, or (b) no circuit of size $subexp(s)$ can approximate $f$ over $\mathcal{E}$ with probability noticeably higher than $1/2$.
We also give more examples of synergy between these two assumptions from cryptography and proof complexity. In particular, we prove that together they imply $NP\not\subseteq io SIZE[2^{n^{o(1)}}]$, and hence that subexponentially-secure one-way functions and public-key encryption exist.
Our conditional NP-hardness results complement the recent results of Hirahara and Ilango (FOCS 2025) which prove conditional NP-hardness of constant-gap MCSP under quasipolynomial-time non-Levin reductions, from seemingly much stronger assumptions.
