2026-07-23T16:50:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27051 2026-07-23T11:36:18Z ddc:004 open_access

Hardness of Computing Nondeterministic Kolmogorov Complexity Hu, Jinqiao Lu, Zhenjian Oliveira, Igor C. meta-complexity average-case complexity Kolmogorov complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jinqiao Hu and Zhenjian Lu and Igor C. Oliveira 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.9 urn:nbn:de:0030-drops-270516 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.9 eng https://creativecommons.org/licenses/by/4.0/legalcode