Metraipolis › archive › dc_0bfee141a734
Asymmetry and Complexity of Nondeterministic Computations — arXiv:2610.20188
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.20188
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T14:37:58.135Z
- SHA-256 of the archived text
939bc51161556dcb50bc19d27ec2c935212e9f0f52c976a682c79c39e32d5b3b- Stable URL of this page
https://metraipolis.com/documento/dc_0bfee141a734
How to cite
Asymmetry and Complexity of Nondeterministic Computations — arXiv:2610.20188 — arXiv (en), https://arxiv.org/abs/2610.20188 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0bfee141a734 (Metraipolis archive dc_0bfee141a734, sha256 939bc51161556dcb50bc19d27ec2c935212e9f0f52c976a682c79c39e32d5b3b)
BibTeX
@misc{dc0bfee141a734,
title = {Asymmetry and Complexity of Nondeterministic Computations — arXiv:2610.20188},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.20188},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0bfee141a734; sha256 939bc51161556dcb50bc19d27ec2c935212e9f0f52c976a682c79c39e32d5b3b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.20188. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno). Categorie arXiv: Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2610.20188 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-15T13:59:54.797Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).