Symmetry of information reveals complexity gaps in nondeterministic computation
Asymmetry and Complexity of Nondeterministic Computations
Computational Complexity
Summary
Symmetry of Information (SoI) is a principle in computer science that helps understand how much information two things share. The authors studied SoI in the context of nondeterministic computations, which are a type of computation where multiple outcomes are possible. They found that whether SoI holds true here is a subtle issue linked to big open problems in computer complexity and cryptography. Their work reveals new connections between SoI, meta-complexity (complexity about complexity itself), and explicit algorithm constructions, leading to stronger guarantees about the limits of what nondeterministic computations can achieve.
What this means in practice
- •For complexity theorists: Guide design of complexity class separations by showing constraints if symmetry of information holds in nondeterministic models.
- •For cryptography engineers: Inform limitations in cryptographic security models related to nondeterministic computations and inform underlying hardness assumptions.
A theory result. No direct application yet.
Authors
Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira
Abstract
Symmetry of Information (SoI) [ZL70] is a fundamental theorem of classical Kolmogorov complexity whose status for time-bounded computation is closely related to central open problems in complexity theory and cryptography. In a recent development, [HMO26] showed that SoI fails for $rKt$ complexity, namely in the setting of randomized computation. By contrast, many basic properties of Kolmogorov complexity are known to remain valid in the presence of nondeterminism [HLO26], suggesting that SoI may provide a fruitful structural principle for exploring the relative power of randomness and nondeterminism in computation. Our results reveal that the validity of SoI for nondeterministic computation, namely for $nKt$ complexity, is a subtle question connected to several frontiers. We show that symmetry of information holds on average for randomized extensions of $nKt$, while its worst case validity would imply breakthrough complexity separations. Although the standard cryptographic argument for asymmetry does not extend to the nondeterministic setting, we provide evidence that information remains asymmetric in nondeterministic computations. Among other results, we show that SoI would imply a collapse of exponential time classes to low levels of the polynomial hierarchy. Then, building on the work of [Hir22b, GK22, KK26, HMO26], we develop a general framework connecting symmetry of information, meta-complexity, and explicit constructions in the nondeterministic setting. More precisely, we prove that suitable formulations of these three notions are quantitatively equivalent. We apply different aspects of this correspondence to make progress on complexity lower bounds and on the failure of SoI for nondeterministic computation. These consequences are unconditional and provide some of the strongest known lower bounds in meta-complexity.