DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.9

Hardness of Computing Nondeterministic Kolmogorov Complexity

Authors: Jinqiao Hu, Zhenjian Lu, and Igor C. Oliveira

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

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 NP is a central research direction. A longstanding open problem in this area is to establish the NP-hardness of MINKT (Ker-I Ko, 1991 [Ker{-}I Ko, 1991]), the problem of estimating time-bounded Kolmogorov complexity. We contribute to this research direction by studying nK^t, a natural variant of Kolmogorov complexity that captures the complexity of representing a string using time-bounded nondeterministic computations [Buhrman et al., 2001]. Let MINnKT denote the task of estimating nK^t(x) of a given input string x. We prove that MINnKT ∈ BPP if and only if NP ⊆ BPP. This can be interpreted as a solution to Ko’s question in the setting of nondeterministic time-bounded Kolmogorov complexity. Crucial to the proof of this result is the investigation of a new notion of probabilistic nondeterministic time-bounded Kolmogorov complexity called pnK^t. This measure can be seen as an extension of pK^t complexity [Halley Goldberg et al., 2022] obtained by replacing 𝖪^t with nK^t. We establish unconditionally that 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 MINpnKT also captures the hardness of NP, and that extending this result to the closely related problem Gap-MINpnKT would imply the exclusion of PH-Heuristica.

Cite as

Jinqiao Hu, Zhenjian Lu, and Igor C. Oliveira. Hardness of Computing Nondeterministic Kolmogorov Complexity. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 9:1-9:50, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.CCC.2026.9,
  author =	{Hu, Jinqiao and Lu, Zhenjian and Oliveira, Igor C.},
  title =	{{Hardness of Computing Nondeterministic Kolmogorov Complexity}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{9:1--9:50},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.9},
  URN =		{urn:nbn:de:0030-drops-270516},
  doi =		{10.4230/LIPIcs.CCC.2026.9},
  annote =	{Keywords: meta-complexity, average-case complexity, Kolmogorov complexity}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.110

Equivalence Between Coding and Complexity Lower Bounds

Authors: Jinqiao Hu, Zhenjian Lu, and Igor C. Oliveira

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

The classical coding theorem in Kolmogorov complexity [Levin, 1974] states that if a string x is sampled with probability ≥ δ by an algorithm with prefix-free domain, then 𝖪(x) ≤ log(1/δ) + O(1). Motivated by applications in algorithms, average-case complexity, learning, and cryptography, computationally efficient variants of this result have been established for several recently introduced probabilistic measures of time-bounded Kolmogorov complexity, including rKt [Zhenjian Lu and Igor C. Oliveira, 2021] and pK^t [Zhenjian Lu et al., 2022]. However, establishing a coding theorem for classical (non-probabilistic) notions of time-bounded Kolmogorov complexity, such as Kt complexity [Leonid A. Levin, 1984], remains a longstanding open problem despite its significance. In particular, the current status of coding results reveals a fundamental gap in our understanding of the role of randomness in data compression. In this work, we make progress by establishing the first equivalence between coding for Kt complexity and complexity lower bounds. Specifically, we show that weak coding for polynomial-time samplable distributions with bounds of the form Kt(x) ≤ (1/δ ⋅ |x|)^ε for all ε > 0 holds if and only if EXP ≠ BPP. Building on this equivalence, we show that similar characterizations hold for non-deterministic and zero-error variants of Kt complexity, demonstrating that coding is equivalent to a corresponding complexity separation in each case. We complement these results by establishing additional equivalences involving the computational hardness of approximating time-bounded Kolmogorov complexity, along with an unconditional lower bound on the complexity of approximating zero-error time-bounded Kolmogorov complexity. These results reveal novel connections between coding (the existence of succinct encodings), complexity separations (e.g., NEXP versus BPP), and meta-complexity (the complexity of deciding if a succinct encoding exists). In particular, our work provides a new perspective on frontier questions in complexity theory and explains why coding theorems exist for rKt and pK^t but remain unknown for other measures of time-bounded Kolmogorov complexity. Finally, our results determine the minimal hardness assumptions sufficient for coding in different settings.

Cite as

Jinqiao Hu, Zhenjian Lu, and Igor C. Oliveira. Equivalence Between Coding and Complexity Lower Bounds. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 110:1-110:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.ICALP.2026.110,
  author =	{Hu, Jinqiao and Lu, Zhenjian and Oliveira, Igor C.},
  title =	{{Equivalence Between Coding and Complexity Lower Bounds}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{110:1--110:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.110},
  URN =		{urn:nbn:de:0030-drops-264991},
  doi =		{10.4230/LIPIcs.ICALP.2026.110},
  annote =	{Keywords: meta-complexity, lower bounds, Kolmogorov complexity}
}

Search Results

Documents authored by Hu, Jinqiao

Hardness of Computing Nondeterministic Kolmogorov Complexity

Abstract

Cite as

Equivalence Between Coding and Complexity Lower Bounds

Abstract

Cite as

Thanks for your feedback!

Could not send message