We investigate central questions in complexity theory through the lens of time-bounded Kolmogorov complexity, focusing on $\textit{nondeterministic}$ measures [AKRR03] and their extensions. In more detail, we consider succinct encodings of a string by programs that may be nondeterministic (nK), randomized (rK), or combine both resources – yielding richer notions such as rnK, pnK, and their generalizations to higher levels of the polynomial hierarchy. Among other contributions, we obtain the following results:

$\textbf{1. Unconditional Complexity Lower Bounds.}$ Let R$_{nKt[s(n)]}$ denote the set of strings $x$ such that nKt$(x) \geq s(|x|)$. We show that R$_{nKt[\gamma\cdot n]} \notin$ NTIME$[2^{o(n)}] \cap$ coNTIME$[2^{o(n)}]$, for every constant $1/2 < \gamma < 1$. For the problem of estimating rnKt complexity, the randomized extension of nKt, we establish lower bounds against AMTIME$[n^{polylog(n)}]$ and SIZE$[n^{polylog(n)}]$. These results can be seen as a significant strengthening of the 15-year old lower bound R$_{nKt[\Omega(n)]} \notin$ NP $\cap$ coNP obtained in [All10, AKRR11], and are among the strongest known $\textit{unconditional}$ lower bounds in meta-complexity.

$\textbf{2. Proof Complexity and Symmetry of Information.}$ [HIL+23, HLO24] showed that cryptographic one-way functions exist if and only if the symmetry of information (SoI) principle $\textit{fails on average}$ for pKt complexity. In contrast, we establish that SoI $\textit{holds on average}$ in the presence of nondeterminism, i.e., pnKt$(x, y) \approx$ pnKt$(y)$ $+$ pnKt$(x | y)$ with high probability if $(x, y)$ is generated by a polynomial-time sampler. On the other hand, we prove that if SoI $\textit{holds in the worst case}$ for pnKt complexity then coNP is not contained in AM. In particular, bridging the gap between average-case and worst-case SoI for pnKt would imply that certain coNP statements do not admit feasible proofs.

$\textbf{3. Average-Case vs Worst-Case Complexity.}$ We consider the longstanding problem of relating the average-case and worst-case complexities of the polynomial hierarchy (PH), i.e., showing that DistPH $\subseteq$ AvgBPP implies PH $\subseteq$ BPP. Building on [Hir20, HLO25], we prove that this implication holds if and only if Gap$\text{-}$MINpKT$^{PH} \in$ prBPP implies Mild$\text{-}$Gap$\text{-}$MINpKT$^{PH} \in$ prBPP, i.e., the complexities of approximating pKt with an oracle to PH with respect to different approximation regimes are related. Consequently, progress on the meta-complexity of nondeterministic variants of Kolmogorov complexity is $\textit{unavoidable}$ in order to understand the average-case complexity of the polynomial hierarchy.

These results reveal deep links between $\textit{complexity theory}$ and $\textit{nondeterministic Kolmogorov complexity}$, pointing to several directions for further research.