Meta-complexity investigates the complexity of computational problems and tasks that are themselves about computations and their complexity. Understanding whether such problems can capture the hardness of $\mathsf{NP}$ is a central research direction. A longstanding open problem in this area is to establish the $\mathsf{NP}$-hardness of $\mathsf{MINKT}$ [Ko91], the problem of estimating time-bounded Kolmogorov complexity.
We contribute to this research direction by studying $\mathsf{nK}^t$, a natural variant of Kolmogorov complexity that captures the complexity of representing a string using time-bounded nondeterministic computations [BFL01]. Let $\mathsf{MINnKT}$ denote the task of estimating $\mathsf{nK}^t(x)$ of a given input string $x$. We prove that $\mathsf{MINnKT} \in \mathsf{BPP}$ if and only if $\mathsf{NP}\subseteq\mathsf{BPP}$. In contrast with prior work, this result provides the first non-conditional, non-oracle, non-partial version of a natural meta-computational problem whose hardness characterizes $\mathsf{NP} \nsubseteq \mathsf{BPP}$.
Crucial to our result is the investigation of a new notion of probabilistic nondeterministic time-bounded Kolmogorov complexity called $\mathsf{pnK}^t$. This measure can be seen as an extension of $\mathsf{pK}^t$ complexity [GKLO22] obtained by replacing $\mathsf{K}^t$ with $\mathsf{nK}^t$. We establish unconditionally that $\mathsf{pnK}^t$ has nearly all key properties of (time-unbounded) Kolmogorov complexity, such as language compression, conditional coding, and a form of symmetry of information. Finally, we show that the corresponding meta-computational problem $\mathsf{MINpnKT}$ also captures the hardness of $\mathsf{NP}$, and that extending this result to the closely related problem $\mathsf{Gap}\text{-}\mathsf{MINpnKT}$ would imply the exclusion of $\mathsf{PH}$-Heuristica.
Improved introduction and techniques overview.
Meta-complexity investigates the complexity of computational problems and tasks that are themselves about computations and their complexity. Understanding whether such problems can capture the hardness of $\mathrm{NP}$ is a central research direction. A longstanding open problem in this area is to establish the $\mathrm{NP}$-hardness of $\mathrm{MINKT}$ [Ko91], the problem of estimating time-bounded Kolmogorov complexity.
We contribute to this research direction by studying $\mathrm{nK}^t$, a natural variant of Kolmogorov complexity that captures the complexity of representing a string using time-bounded nondeterministic computations [BFL01]. Let $\mathrm{MINnKT}$ denote the task of estimating $\mathrm{nK}^t(x)$ of a given input string $x$. We prove that $\mathrm{MINnKT} \in \mathrm{BPP}$ if and only if $\mathrm{NP}\subseteq\mathrm{BPP}$. In contrast with prior work, this result provides the first non-conditional, non-oracle, non-partial version of a natural meta-computational problem whose hardness characterizes $\mathrm{NP} \not\subseteq \mathrm{BPP}$.
Crucial to our result is the investigation of a new notion of probabilistic nondeterministic time-bounded Kolmogorov complexity called $\mathrm{pnK}^t$. This measure can be seen as an extension of $\mathrm{pK}^t$ complexity [GKLO22] obtained by replacing $\mathrm{K}^t$ with $\mathrm{nK}^t$. We establish unconditionally that $\mathrm{pnK}^t$ has nearly all key properties of (time-unbounded) Kolmogorov complexity, such as language compression, conditional coding, and a form of symmetry of information. Finally, we show that the corresponding meta-computational problem $\mathrm{MINpnKT}$ also captures the hardness of $\mathrm{NP}$, and that extending this result to the closely related problem $\mathrm{Gap}$-$\mathrm{MINpnKT}$ would imply the exclusion of $\mathrm{PH}$-Heuristica.
