arXiv CSopen access

Witness Complexity of Short Descriptions: A Cryptographic Perspective

Witness Complexity of Short Descriptions: A Cryptographic Perspective Fabio F.G. Buono Independent Researcher

arXiv:2606.31370v1 [cs.CR] 30 Jun 2026

ORCID: 0009-0004-9199-2793

July 1, 2026 Abstract In cryptographic practice, a short key or certificate is useful only if it can be decompressed or verified within an acceptable time budget; a compact representation that requires superpolynomial work to expand offers no operational guarantee within a bounded-time protocol. This paper formalises that gap by introducing witness complexity γ(x), the minimum running time over all near-shortest descriptions of a string x on a universal Turing machine. The quantity γ(x) is distinct from both Shannon entropy and Kolmogorov complexity K(x): an object may have low descriptive complexity yet high γ(x), if its near-shortest descriptions are computationally expensive to execute. We establish five main results: invariance of γ up to polynomial factors across universal machines (A); a conditional separation showing that low K does not imply polynomial decompressibility, assuming P ̸= NP (B); an unconditional lower bound on γ, assuming only the classical incomputability of K (B’); an exact biconditional characterisation of P = NP in terms of the class-relative variant γP , restricted to certificates whose Kolmogorov complexity is commensurate with the instance size (C); and unconditional polynomial-time tractability on structurally guided families of NP instances (D). To the authors’ knowledge, γP is the only measure admitting such a biconditional characterisation of P = NP in the standard Turing model. Part II introduces three companion quantities measuring work per bit of genuine input information, overhead beyond writing the output, and information density of solutions, and develops their interaction with γ. An application to grammar-based compression exhibits an unconditional gap between grammar size and derivation cost invisible to all existing measures. A falsifiable conjecture connects the framework to the observed tractability of industrial NP instances. Collectively, the results position γ as a metric for the usability of keys and certificates: low K(x) alone is insufficient; low γP (x) is required for a short description to be operationally accessible within a bounded-time protocol.

Contents 1 Introduction and Standing Hypotheses 1.1 Cryptographic motivation and the gap this paper fills . . . . . . . . . . . . 1.2 Technical contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

3 3 4

1.3 1.4

Standing hypotheses and model of computation . . . . . . . . . . . . . . . Organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 6

2 Definitions

6

3 Basic Properties

9

4 Main Results 4.1 Theorem A: Invariance of γ . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Theorem B: Conditional Separation of K and γP . . . . . . . . . . . . . . 4.3 Theorem C: Exact Characterisation of P = NP . . . . . . . . . . . . . . . 4.4 Theorem B’: Unconditional Lower Bound on γ . . . . . . . . . . . . . . . . 4.5 Theorem D: Tractability on Structurally Guided Families . . . . . . . . . . 4.6 Conjecture: Uniform Witness Representation . . . . . . . . . . . . . . . . .

11 11 12 13 15 16 17

5 Separation Examples

17

6 Discussion and Related Work 6.1 Relation to prior complexity measures . . . . . . . . . . . . . . . . . . . . 6.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Efficiency ratios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19 19 20 20

7 Threat Model and Cryptographic Implications 7.1 Assets, adversary, and relevant metrics . . . . . . . . . . . . . . . . . . . . 7.2 Implications of the main theorems . . . . . . . . . . . . . . . . . . . . . . . 7.3 Attack scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21 21 21 22

8 Application: Grammar-Based Compression 8.1 Background: the Smallest Grammar Problem . . . . . . . . . . . . . . . . 8.2 Grammar witness complexity . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 The gap lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23 23 23 23

9 Open Questions

25

What Part I Establishes

26

Part II: Companion Quantities

26

10 Adaptive Complexity

27

11 Output Overhead Complexity

28

12 Structural Entropy

29

13 Summary: Four Quantities

30

Conclusion

32

Further Directions

32

2

A Classical Measures as Limiting Regimes; Grammar Gap Details 32 A.1 Classical measures as limiting regimes of γ . . . . . . . . . . . . . . . . . . 33 A.2 Full proof of Lemma 8.2: grammar complexity gap . . . . . . . . . . . . . 33 B Full Proof of Theorem B’: Unconditional Lower Bound on γ

34

C An Optimal Decompressor Incurs Only Constant Overhead Beyond Its Output 35

1

Introduction and Standing Hypotheses

1.1

Cryptographic motivation and the gap this paper fills

A central assumption in cryptographic protocol design is that a compact representation of a key, certificate, or witness can be used within a bounded time budget: key schedules must be derivable in real time, certificates must be verifiable before a session times out, and proof-carrying data must be decompressible at the point of verification. This assumption is operationally necessary but has not been formalised as a complexity-theoretic invariant. Three classical measures of information have coexisted without addressing it. Kolmogorov complexity K(x) [8, 11] measures the length of the shortest description of x, but says nothing about the computational cost of using that description. Shannon entropy [14] measures the average description length for a source, with encoding and decoding costs assumed away. Chaitin’s Ω [2] encodes all halting information in the extreme where no description is computationally accessible. None of these measures asks: given that a short description exists, how much work is required to execute it? This paper introduces γ(x), the witness complexity of x, defined as the minimum running time over all near-shortest descriptions of x on a fixed universal prefix Turing machine (Definition 2.1). The quantity γ(x) is the answer to the question above. Its classrelative version γP (x) = γP (x) restricts the decompressor to polynomial-time machines and is the principal object of study (Definition 2.6). Cryptographic objective. The cryptographic goal of this paper is to provide a formal basis for reasoning about the usability of compact representations. Concretely, γP (x) being polynomial in the relevant instance size is a sufficient condition for x to be operationally accessible within a polynomial-time protocol via a near-shortest encoding; it is also necessary among decompressors that operate on near-shortest descriptions (Definition 2.6). The framework applies to three cryptographic scenarios. (i) Key management. A key k of length ℓ may be stored as a near-shortest description d with |d| ≈ K(k). The key is usable in a protocol only if γP (k) is polynomial in the security parameter; otherwise the derivation cost exceeds the protocol budget. (ii) Certificate verification. An NP certificate c for an instance w may be encoded compactly as a near-shortest description. A sufficient condition for the certificate to be recoverable within a polynomial-time protocol via such an encoding is that γP (c) is polynomial in |w|. (iii) Key-schedule and PRNG expansion. A pseudorandom generator with seed s of length k ≪ n produces output of length n. The seed is a near-shortest description 3

of the output; the expansion cost satisfies γ(output) ≥ n (at least n steps are needed to write all output bits) and γ(output) ≤ TPRNG (s), where TPRNG (s) is the running time of the generator on seed s. The γ framework makes this cost explicit and comparable across constructions. The threat model and attack scenarios arising from large γP values are formalised in Section 7.

1.2

Technical contributions

We prove the following results, stated informally here and formally in Sections 2–4. (A) Invariance (Theorem 4.2). For any two universal prefix Turing machines U1 , U2 , there exists a polynomial q such that γU1 (x) ≤ q(|x|) · γU2 (x) + O(1) for all x. The polynomial factor is made explicit via a compiler lemma (Lemma 4.1). This invariance establishes γ as a machine-independent complexity measure, a prerequisite for its use in any protocol-independent security argument. (B) Conditional separation (Theorem 4.4). Assuming P ̸= NP, there exists an explicit infinite family {xφ } indexed by Boolean formulas such that K(xφ ) = O(|φ|) and γP (xφ ) is superpolynomial in |φ|. Under P ̸= NP, the existence of a short description does not imply polynomial decompressibility. (C) Exact characterisation of P = NP (Theorem 4.7). In the standard multi-tape deterministic Turing model: P = NP if and only if for every L ∈ NP there exists a polynomial pL such that for every instance w of L there exists a valid certificate xw with K(xw ) = Ω(|w|) and γP (xw ) ≤ pL (|w|). The K(xw ) = Ω(|w|) condition is necessary: for KC-poor certificates, γP = ∞ unconditionally (Remark 4.8). The non-trivial direction (⇐) uses a dovetailing schedule (Lemma 4.6) together with a fixed-machine argument that reduces the search to polynomially many candidates. (B’) Unconditional lower bound (Theorem 4.10, Appendix B). Assuming only the classical incomputability of K: for every polynomial p, there exists y with γ(y) > p(|y|). This result is unconditional and complementary to (B). (D) Tractability on structured families (Theorem 4.16). If F is a structurally guided family for L ∈ NP (Definition 4.13): a family where a polynomial-time procedure PF produces, for each x ∈ F , a near-shortest description d of a valid witness yx that is also expandable to yx in time ≤ p(|x|) for a fixed polynomial p, then L is solvable in polynomial time on F . The result is unconditional and does not require P = NP. Part II (Sections 10–13) introduces three companion quantities: adaptive complexity Tad (A, x) = TA (x)/K(x) (work per bit of genuine input information), output overhead complexity OCout (A, x) = TA (x)−|A(x)| (overhead beyond writing the output A(x)), and structural entropy Hs (y) = K(y)/ log2 |y| (information density of solutions). An application to grammar-based compression (Section 8) exhibits an unconditional gap between grammar size and derivation depth, invisible to all existing measures (Lemma 8.2).

4

1.3

Standing hypotheses and model of computation

Throughout this paper the following hypotheses hold without further notice. (H1) A universal prefix Turing machine U is fixed once and for all. All Kolmogorov complexities K(x) are defined with respect to U . We denote by c0 a fixed constant depending only on U (not on x) such that for every x ∈ {0, 1}∗ there exists a selfdelimiting program d with U (d) = x and |d| ≤ K(x) + c0 . Such a constant exists because K(x) is the infimum of program lengths and the infimum is achieved up to a fixed slack by the definition of the universal machine [11]. The value of c0 is chosen large enough to also absorb the constant overhead of the identity instruction (used in upper bound arguments throughout the paper) and of any fixed O(1)-length protocol π appearing in near-shortest descriptions (such as the protocol used in the construction of Theorem 4.4). All asymptotic results are stated up to such additive constants. (H2) The standard model of computation is the multi-tape deterministic Turing machine. Running times TM (d) count the total number of steps of M on input d, including the time to read d. All complexity classes (P, NP, and their relativised versions) are defined with respect to this model unless explicitly stated otherwise. (H3) All programs d considered are self-delimiting (prefix-free): U halts and reads exactly the bits of d without an explicit end-of-input marker. This is the standard setup for prefix Kolmogorov complexity [11]. In particular, K(x) > 0 for every nonempty x ∈ {0, 1}∗ (with the exact lower bound depending on U as per (H1)), and K(ε) = O(1) for the empty string ε. (H4) Unless otherwise stated, x, y, d ∈ {0, 1}∗ . The length of a string s is denoted |s|. The empty string is denoted ε. (H5) P is the class of languages decidable by a deterministic Turing machine (hypothesis (H2)) in time polynomial in the input length. NP is the class of languages for which there exists a deterministic polynomial-time verifier: L ∈ NP if and only if there exist a polynomial q and a deterministic polynomial-time machine V such that for every w ∈ {0, 1}∗ : w ∈ L ⇐⇒ ∃ c ∈ {0, 1}q(|w|) with V (w, c) = 1. The string c is called a witness (or certificate) for w. We write γP (x) for γP (x) throughout. (H6) SAT denotes the Boolean satisfiability problem: given a propositional formula φ in conjunctive normal form, decide whether there exists a truth assignment satisfying φ. SAT is NP-complete [4]: every language in NP reduces to SAT in polynomial time, and SAT ∈ NP. We use SAT as the canonical NP-complete language; all results referencing SAT hold equivalently for any NP-complete language. The invariance theorem [8, 11] guarantees that for any two universal prefix machines U1 , U2 there exists a constant c12 , depending only on U1 and U2 and not on x, such that KU1 (x) ≤ KU2 (x) + c12 . All results below are robust to the choice of U within this additive constant. 5

1.4

Organisation

Section 2 introduces the definitions (witness complexity, class-relative witness complexity, description game). Section 3 establishes basic properties and lower bounds. Section 4 states and proves the five main results (Theorems A, B, C, B’, D), with proof sketches in the body and full proofs in the appendices where indicated. Section 5 exhibits the separation examples. Section 6 discusses related work and the relation to prior complexity measures. Section 7 formalises the threat model and cryptographic implications. Section 8 applies the framework to grammar-based compression. Section 9 lists open questions. Part II (Sections 10–13) introduces the companion quantities Tad , OCout , and Hs . Appendix A derives the classical measures as limiting regimes of γ. Appendix B proves Theorem B’ (unconditional lower bound) in full. Appendix C establishes that an optimal decompressor incurs only constant overhead beyond writing its output.

2

Definitions

Throughout this section, U is the universal prefix Turing machine fixed in hypothesis (H1), and all strings are over {0, 1}∗ as per hypothesis (H4). Definition 2.1 (Witness complexity). For x ∈ {0, 1}∗ , the witness complexity of x is γ(x) =

min d : U (d)=x |d|≤K(x)+c0

TU (d),

where TU (d) denotes the total number of steps of U on input d (including the time to read d), and c0 is the fixed additive constant from hypothesis (H1). The minimisation is over all near-shortest descriptions of x, i.e. self-delimiting programs d that produce x and whose length exceeds K(x) by at most c0 . The set of near-shortest descriptions is non-empty by definition of K(x). Since U (d) = x implies that U halts on d, the value TU (d) is finite for every d in the set; the minimum of a non-empty collection of finite values is therefore well-defined and finite. Informally: γ(x) is the minimum decompression time over all near-shortest descriptions of x. It measures not the existence of a compact representation, but the computational cost of using one. Remark 2.2 (Why near-shortest, not shortest). One could define γ by minimising TU (d) over the single shortest description d∗ achieving K(x). The present definition is strictly more general: the set of near-shortest descriptions can contain programs with very different running times, and the minimum over this set may be substantially smaller than the time of d∗ alone. Restricting to the exact shortest description would make γ depend on the arbitrary choice of d∗ when several descriptions achieve K(x). The additive slack c0 absorbs the ambiguity, is independent of x, and does not affect the asymptotics of any result in this paper. The choice mirrors the standard treatment of K t in time-bounded Kolmogorov complexity [11]. Example 2.3 (Witness complexity: three canonical cases). (i) Incompressible string. Let x ∈ {0, 1}n with K(x) ≥ n − c0 . Every program d with U (d) = x satisfies |d| ≥ K(x) ≥ n − c0 ; reading d requires at least |d| steps, so γ(x) ≥ n − c0 = Ω(n). The description consisting of x prefixed by the O(1)-bit identity instruction (the fixed program that copies its input to output) satisfies |d| = n + O(1) ≤ K(x) + c0 and TU (d) = O(n), giving γ(x) = Θ(n). 6

(ii) Highly compressible string. Let x = 0n (the all-zeros string of length n). A description d of length O(log n) encodes the pair (n, “print n zeros”); the machine runs in time O(n) to produce all n output bits. Thus K(x) = O(log n) and γ(x) = Θ(n): the description is short but executing it takes linear time. (iii) Low K, potentially high γ. The family {xφ } of Theorem 4.4 has K(xφ ) = O(|φ|) and, under P ̸= NP, γP (xφ ) superpolynomial. This is the central separation example of the paper and is constructed in full in Section 4. Remark 2.4 (Cryptographic interpretation of Definition 2.1). In a cryptographic context, d plays the role of a compressed key or compact certificate: it is the short representation that is stored or transmitted. U (d) = x is the key expansion or decompression step. TU (d) is the derivation cost: the number of computational steps required to recover the full object x from its compact form d. γ(x) is therefore the minimum derivation cost over all near-shortest compact representations of x. A small γ(x) means that x has a compact representation that can be expanded cheaply; a large γ(x) means that every compact representation is expensive to expand, regardless of which one is chosen. Definition 2.5 (Description game). The following two-player game gives an operational characterisation of γ(x) equivalent to Definition 2.1. Throughout, U is the universal machine fixed in hypothesis (H1). • Player A, knowing x, selects a description d with U (d) = x and |d| ≤ K(x) + c0 . • Player B receives d and runs U (d). The cost of the game is TU (d). Then γ(x) = mind TU (d) over all of Player A’s admissible choices. The game separates the cost of finding a short description (Player A’s problem, not measured by γ) from the cost of using one (Player B’s problem, which γ measures). Cryptographic reading: Player A is the key generator or certificate issuer; Player B is the protocol participant who must expand or verify. γ(x) is the minimum expansion cost that Player A can guarantee Player B, optimised over all admissible compact representations of x. Definition 2.6 (Class-relative witness complexity). Let C be a class of Turing machines. The C-relative witness complexity of x ∈ {0, 1}∗ is γC (x) =

min

d : |d|≤K(x)+c0 M ∈C, M (d)=x

TM (d).

The length constraint is on |d| (the description), not on |x| (the object): the decompressor M receives a short description and produces a possibly much longer object. If no M ∈ C reconstructs x from any near-shortest description, set γC (x) = ∞. The principal case is C = P, the class of polynomial-time deterministic Turing machines (hypothesis (H5)), giving γP (x) = γP (x). We write γP (x) throughout for this case.

7

Remark 2.7 (Finiteness of γP (x) for NP instances). For the results of Section 4 to be non-vacuous, it is necessary that γP (xw ) be finite for the certificates xw appearing in Theorem 4.7. In the direction (⇒) of Theorem 4.7 (assuming P = NP), the standard self-reducibility argument shows that for every L ∈ NP there exists a polynomial-time algorithm A that both decides L and, when w ∈ L, outputs a witness (by extending a candidate certificate bit by bit, using the decision procedure as a subroutine; see e.g. [11]). Under the condition K(xw ) = Ω(|w|) of Theorem 4.7, the description dw = ⟨w, πA ⟩ is near-shortest for xw = (1, c′w ) (where c′w is the KC-rich witness of Theorem 4.7’s proof), and the decompressor Mc′w ∈ P — which runs A and appends a fixed pad r stored in its description — achieves γP (xw ) ≤ TMc′ (dw ) = poly(|w|). When K(xw ) ≪ |w|, the w compact encoding of xw cannot be expanded in poly(K(xw )) steps by any M ∈ P (since |xw | ≫ poly(K(xw ))), and γP (xw ) = ∞; this is itself an instance of the separation between descriptive and computational complexity established in this paper. In the direction (⇐), γP (xw ) being finite and polynomial is an explicit hypothesis. No case in Section 4 requires γP to be finite without explicit justification. Example 2.8 (Class-relative witness complexity: cryptographic instances). (i) Key derivation. Let x be a session key derived from a master secret s via a key-derivation function KDF. Since KDF is a fixed deterministic function, K(x) ≤ K(s) + O(1) (given s, a constant-length instruction suffices to reconstruct x). If additionally s is incompressible (K(s) = |s| − O(1)) and KDF does not introduce further compressibility (K(x) ≥ K(s) − O(1)), then d = s satisfies |d| = |s| ≤ K(x) + O(1), making it a near-shortest description of x. Under these conditions, γP (x) ≤ TKDF (s): the derivation cost bounds γP from above. (ii) Proof-carrying data. Let x = (w, π) where π is an NP proof for instance w. A nearshortest description d of x may encode the proof generation procedure. γP (x) is the minimum cost of a polynomial-time machine to recover (w, π) from d; if γP (x) = ∞, no compact encoding of the proof is efficiently decompressible. (iii) PRNG output. Let x be the output of a PRNG with seed s, |s| = k, |x| = n ≫ k. The seed s is a near-shortest description of x. Since writing n output bits requires at least n steps, γ(x) ≥ n. The running time of the generator gives an upper bound: γ(x) ≤ TPRNG (s). Since the generator must produce n output bits, TPRNG (s) ≥ n regardless of k. Therefore γ(x) = Θ(n) unconditionally. As for γP : any M ∈ P that expands s to x runs in poly(|s|) = poly(k) time. This is consistent with γ(x) ≥ n only if poly(k) ≥ n, i.e. n = O(poly(k)). If n is superpolynomial in k, no polynomial-time-in-|s| machine can produce x (since poly(k) < n steps suffice to write at most poly(k) < n output bits), so γP (x) = ∞. Remark 2.9 (Relationship to K t and Kt). Two related measures appear in the literature. Time-bounded Kolmogorov complexity K t (x) = min{|d| : U (d) = x in ≤ t steps} fixes a time bound t and minimises description length. γ fixes the length constraint (nearminimal) and minimises time. The questions are dual in direction: K t asks “how short can the description be if we cap the time?”; γ asks “how fast can we decompress if we insist on a near-shortest description?” Levin’s Kt complexity Kt(x) = mind {|d| + log TU (d) : U (d) = x} combines length and log-time into a single quantity [10, 11]. The spectrum K −→ K t −→ Kt −→ γ 8

represents increasing sensitivity to computational cost: K ignores cost entirely; K t caps it; Kt penalises it logarithmically; γ minimises it directly subject to the near-shortest constraint. To the authors’ knowledge, γ has not previously been studied as a standalone invariant.

3

Basic Properties

This section establishes lower bounds on γ(x) and γC (x) that hold unconditionally, without any hypothesis on P = NP. All results follow directly from the definitions in Section 2 and the standing hypotheses of Section 1.3. Proposition 3.1 (Lower bound from description length). For every x ∈ {0, 1}∗ , γ(x) ≥ K(x). Proof. Every program d with U (d) = x satisfies |d| ≥ K(x) by definition of K(x) as the length of the shortest self-delimiting program producing x. Reading d requires at least |d| steps (hypothesis (H2)), so TU (d) ≥ |d| ≥ K(x). Since this holds for every d in the minimisation set of Definition 2.1, taking the minimum gives γ(x) ≥ K(x). Remark 3.2 (Tightness of Proposition 3.1). The bound is tight up to constant factors: for x = 0n one has K(x) = O(log n) and γ(x) = Θ(n) (Example 2.3(ii)), so the gap between γ(x) and K(x) can be arbitrarily large. For incompressible strings x with K(x) = Θ(n), Proposition 3.3 below shows the bound is achieved up to constants. Cryptographic implication: Proposition 3.1 says that the derivation cost is always at least the information content of the object. No compact representation can be expanded faster than reading it: even in the best case, γ(x) ≥ K(x). Proposition 3.3 (Lower bound in the incompressible regime). For every x ∈ {0, 1}∗ with K(x) = Ω(|x|), γ(x) = Θ(|x|). Proof. Lower bound. By hypothesis K(x) ≥ c1 |x| for a positive constant c1 . By Proposition 3.1, γ(x) ≥ K(x) ≥ c1 |x| = Ω(|x|). Upper bound. The description d consisting of x prefixed by the O(1)-bit identity instruction (the fixed program of U that copies its input to output) satisfies |d| = |x| + O(1). Since every string has a description of length |x| + O(1) (the identity description), K(x) ≤ |x| + O(1); combined with the hypothesis K(x) ≥ c1 |x|, we get K(x) = Θ(|x|), so |d| = |x| + O(1) ≤ K(x) + c0 for all sufficiently large |x|. Thus d is a near-shortest description of x. The machine U on input d copies |x| bits to output in O(|x|) steps, giving TU (d) = O(|x|). Therefore γ(x) = O(|x|). Combining the two bounds: γ(x) = Θ(|x|). Remark 3.4 (The compressible regime). For objects with K(x) ≪ |x| (highly compressible), the lower bound of Proposition 3.1 may be far below |x|. In this regime γ(x) can range anywhere from Ω(K(x)) to values exceeding |x|: • γ(x) = Θ(K(x)): some near-shortest description of x is also among the fastest to execute. Example: a string x whose near-shortest description d is a lookup table; U (d) copies the table in O(|d|) = O(K(x)) steps. 9

• γ(x) = Θ(|x|): the short description requires linear work to expand. Example: x = 0n , K(x) = O(log n), γ(x) = Θ(n) (Example 2.3(ii)). • γP (x) superpolynomial in |x| while γ(x) may be smaller: under P ̸= NP, the family {xφ } of Theorem 4.4 achieves K(xφ ) = O(|φ|) with γP (xφ ) superpolynomial (no polynomial-time decompressor exists), while γ(xφ ) may still be finite via a nonpolynomial-time machine. This is the central separation example of the paper. Section 5 exhibits concrete examples spanning all three regimes. Proposition 3.5 (Trivial upper bound). For every x ∈ {0, 1}n , γ(x) ≤ n + O(1). Proof. The identity description d (the string x prefixed by the O(1)-bit identity instruction) satisfies |d| = n + O(1). Since the identity description itself witnesses K(x) ≤ n + O(1), we have |d| ≤ K(x) + c0 (by the choice of c0 in hypothesis (H1), which is large enough to absorb the identity-instruction overhead), so d is a near-shortest description of x. The machine U on d copies n bits to output in TU (d) = n + O(1) steps. Hence γ(x) ≤ n + O(1). Remark 3.6 (Boundary case: empty string). For the empty string ε: K(ε) = O(1) (hypothesis (H3)), and any near-shortest description d of ε has length O(1). The machine U on such d produces no output and halts in O(1) steps, giving γ(ε) = O(1). This is consistent with Proposition 3.1 (γ(ε) ≥ K(ε) = O(1), which imposes no non-trivial lower bound) and with Proposition 3.5 (γ(ε) ≤ 0 + O(1) = O(1)). Proposition 3.7 (Monotonicity of γC in C). If C1 ⊆ C2 as classes of Turing machines, then γC2 (x) ≤ γC1 (x) for all x. Proof. Every decompressor M ∈ C1 is also in C2 , so the set over which the minimum is taken in γC2 (x) is a superset of the one in γC1 (x). A minimum over a larger set is at most the minimum over a smaller set. Remark 3.8 (Relation between γ and γP ). Definition 2.1 defines γ(x) via the fixed universal machine U , while Definition 2.6 defines γC (x) via a minimum over machines in C. These two notions coincide up to polynomial factors when C is the class of all Turing machines, by the simulation argument of Theorem 4.2: every Turing machine M is simulable by U with polynomial overhead, so γ(x) ≤ poly(|x|) · γall TM (x). For the purposes of comparing γ with γP , Proposition 3.7 with C1 = P ⊆ C2 = all TM gives γall TM (x) ≤ γP (x) whenever γP (x) < ∞; combined with the simulation bound above, γ(x) ≤ poly(|x|)·γP (x) whenever γP (x) < ∞. Strict inequality γ(x) < γP (x) is possible: γ(x) allows any Turing machine as decompressor, while γP (x) restricts to P. If γP (x) = ∞ (no polynomial-time machine reconstructs x from a near-shortest description), then γ(x) may still be finite, achieved by a non-polynomial decompressor. Cryptographic implication: γP (x) = ∞ means no compact representation of x is efficiently recoverable by a polynomial-time verifier, regardless of which near-shortest description is used. Such an x cannot serve as a usable key or certificate in any polynomial-time protocol.

10

4

Main Results

This section states and proves the five main results of the paper. Each theorem is presented with its formal hypotheses, a proof sketch in the body sufficient to verify the strategy and key steps, and a pointer to the appendix for the complete proof where the argument is long. All theorems that reference γP implicitly assume hypothesis (H5); all results are in the multi-tape deterministic Turing model of hypothesis (H2).

4.1

Theorem A: Invariance of γ

We first establish the compiler lemma that makes the polynomial factor in Theorem A explicit. Lemma 4.1 (Compiler simulation). Let U1 , U2 be two universal prefix Turing machines. There exist a computable map C : {0, 1}∗ → {0, 1}∗ and constants cC , CC , kC ≥ 1 depending only on U1 , U2 such that for every program p with U2 (p) = x: (i) U1 (C(p)) = x, (ii) |C(p)| ≤ |p| + cC , (iii) TU1 (C(p)) ≤ CC · |p|kC · TU2 (p) + CC . Proof. Construct C as the map that prefixes p with a fixed cC -bit header encoding an interpreter for U2 ’s instruction set together with an I/O wrapper. The header length cC depends only on U1 and U2 . Condition (i) holds because U1 on C(p) first executes the interpreter, which faithfully simulates U2 on p and produces x. Condition (ii) holds because |C(p)| = |p| + cC . Condition (iii) holds because each step of U2 on p is simulated by U1 in O(|p|kC ) steps (the overhead of the interpreter, bounded polynomially in |p|), giving total time CC · |p|kC · TU2 (p) + CC . Theorem 4.2 (A — Invariance of γ). For any two universal prefix Turing machines U1 , U2 , there exists a polynomial q such that for all x ∈ {0, 1}∗ : γU1 (x) ≤ q(|x|) · γU2 (x) + O(1), and symmetrically with U1 and U2 exchanged. Hence γ is a computational invariant, well-defined up to polynomial factors independently of the choice of universal machine. Cryptographic implication: the invariance guarantees that γP (x) being polynomially bounded is a machine-independent property; it does not depend on which universal machine is used to define K and γ. Proof. Let d be the near-shortest description of x for U2 achieving γU2 (x): so U2 (d) = x, |d| ≤ K(x) + c0 , and TU2 (d) = γU2 (x). Apply Lemma 4.1 to obtain C(d) satisfying: • U1 (C(d)) = x

(by condition (i)),

• |C(d)| ≤ |d| + cC ≤ KU2 (x) + c0 + cC ≤ KU1 (x) + c′0 for a constant c′0 depending only on U1 , U2 (by condition (ii) and the Kolmogorov invariance theorem), • TU1 (C(d)) ≤ CC · |d|kC · γU2 (x) + CC

(by condition (iii)).

11

Since |d| ≤ K(x) + c0 ≤ |x| + c0 + O(1), there exists a polynomial q0 such that CC · |d|kC ≤ q0 (|x|). Therefore C(d) is a near-shortest description of x for U1 , and γU1 (x) ≤ TU1 (C(d)) ≤ q0 (|x|) · γU2 (x) + CC . Setting q = q0 and absorbing CC into the O(1) term gives the stated bound. The symmetric bound follows by exchanging U1 and U2 . Remark 4.3 (Position of Theorem A in the literature). Theorem 4.2 places γ in the same foundational category as K t : a quantity that depends on the universal machine, but only up to a factor independent of x (additive O(1) for K t ; multiplicative polynomial for γ). The invariance is a prerequisite for any application of γ to complexity-theoretic questions, including the characterisation of P = NP in Theorem 4.7. The degree kC of the polynomial and the constants CC , cC can in principle be made explicit for natural subclasses of universal machines; see Question Q4 in Section 9.

4.2

Theorem B: Conditional Separation of K and γP

Theorem 4.4 (B — Conditional separation). Assuming P ̸= NP, there exists an infinite family of Boolean formulas {φi }i≥1 and corresponding strings {xφi } such that: K(xφi ) = O(|φi |)

and γP (xφi ) is superpolynomial in |φi |.

Under P ̸= NP, the existence of a short description does not imply polynomial-time decompressibility. Cryptographic implication: under P ̸= NP, there exist compact witnesses with K linear in the formula size yet not decompressible by any polynomial-time protocol; see Section 7. We first establish the subfamily density lemma used in the proof. Lemma 4.5 (Incompressible subfamily). For every constant c > 0, the set Fc = {φ : K(xφ ) ≥ |φ| − c} is infinite, where xφ is the string defined in the construction below. Proof. Let m = |φ| denote the bit-length of the formula (not the number of variables). For each m, the construction below yields at least 2m distinct strings xφ as φ ranges over formulas of length m (there are 2m binary strings of length m, each a valid formula encoding under a fixed coding scheme). A string has K(xφ ) < m − c only if it admits a self-delimiting description of length < m − c. The number of such programs is at most P k m−c . For sufficiently large m and c > O(1), there are strictly fewer than k<m−c 2 < 2 m 2 such programs, so at least one formula φ of length m satisfies K(xφ ) ≥ m−c = |φ| −c. Hence Fc contains a formula of every sufficiently large length and is infinite. Proof of Theorem 4.4. Construction. For each Boolean formula φ on n variables, define: ( (1, yφ ) if φ ∈ SAT, where yφ is the lex-first satisfying assignment, xφ = (0, 0n ) if φ ∈ / SAT. The leading bit encodes satisfiability. Define the near-shortest description: dφ = ⟨φ, π⟩, 12

where π is a fixed O(1)-length protocol: “run the lex-first-SAT procedure on φ and output (1, y) or (0, 0n ).” Then |dφ | = |φ| + O(1), giving K(xφ ) = O(|φ|). Near-shortness. By Lemma 4.5 applied with c = c0 (the constant of hypothesis (H1)), the subfamily Fc0 is infinite and for every φ ∈ Fc0 the description dφ satisfies |dφ | = |φ| + O(1) ≤ K(xφ ) + c0 , so dφ is a valid near-shortest description. Superpolynomial lower bound. Suppose for contradiction that there exist M ∈ P and a polynomial p such that M (dφ ) = xφ in time ≤ p(|φ|) for every φ ∈ Fc0 . The machine M is fixed (it does not depend on φ); given any φ ∈ Fc0 , construct dφ = ⟨φ, π⟩ in polynomial time and run M (dφ ): if the leading bit is 1, report φ ∈ SAT; if 0, report φ∈ / SAT. This is a correct polynomial-time algorithm for SAT restricted to Fc0 . Since Fc0 is infinite (Lemma 4.5) and contains formulas of every sufficiently large length m, it contains instances of every input size — and in particular both satisfiable and unsatisfiable instances of every large enough length (otherwise SAT restricted to that length would be trivially decidable, which would itself give a polynomial-time algorithm for SAT on all instances by padding, contradicting P ̸= NP). A polynomial-time algorithm that decides SAT correctly on an infinite family containing instances of every length is a polynomial-time algorithm for SAT [4], contradicting P ̸= NP. Therefore no such M and p exist, and γP (xφ ) is superpolynomial for all φ ∈ Fc0 .

4.3

Theorem C: Exact Characterisation of P = NP

We first establish the dovetailing lemma used in the non-trivial direction; the polynomialtime bound is derived in the proof of Theorem 4.7 itself via a fixed-machine argument. Lemma 4.6 (Dovetailing schedule). Suppose there exists a pair (M ∗ , d∗ ) of a Turing machine and a string with |M ∗ | + |d∗ | ≤ S and TM ∗ (d∗ ) ≤ t. Then there exists a procedure D that, running for T = 2S · t total steps, finds and completes the execution of (M ∗ , d∗ ), producing its output. Proof. Fix an enumeration of all pairs (M, d) in order of non-decreasing s = |M | + |d|, breaking ties arbitrarily. Run a time-sharing simulation for T total processor steps, cycling through pairs in enumeration order and advancing each by one simulation step per visit. The good pair (M ∗ , d∗ ) of size s∗ ≤ S occupies a fixed position in the enumeration. The number of pairs of size ≤ S is at most NS ≤ 2S+1 ; in T = 2S · t total steps, each such pair receives at least ⌊T /NS ⌋ ≥ ⌊2S t/2S+1 ⌋ = ⌊t/2⌋ steps. For t ≥ 2, this suffices to complete (M ∗ , d∗ ), producing the output. Application to Theorem 4.7. In that application |M ∗ | = O(1) and |d∗ | = poly(|φ|), so S = poly(|φ|) and the generic bound gives T = 2poly(|φ|) — exponential. The polynomial bound T = poly(|φ|) used in Theorem 4.7 is achieved by a tighter argument: since M ∗ is a fixed machine (independent of φ), one enumerates only descriptions d∗ of length ≤ poly(|φ|), of which there are only polynomially many. The Lemma as stated is invoked only for its general structure; the tight bound is derived in the proof of Theorem 4.7 directly. Theorem 4.7 (C — Exact characterisation of P = NP). In the multi-tape deterministic Turing model (hypothesis (H2)), P = NP if and only if for every L ∈ NP there exists a polynomial pL such that for every w ∈ {0, 1}∗ with w ∈ L there exists a valid certificate xw , a pair (1, cw ) where cw is a witness accepted by the NP verifier of L, satisfying K(xw ) = Ω(|w|) and γP (xw ) ≤ pL (|w|). 13

More explicitly for SAT: P = NP if and only if there exists a polynomial p such that for every satisfiable formula φ there exists a valid certificate xφ = (1, cφ ) (encoding satisfiability and a satisfying assignment) with K(xφ ) = Ω(|φ|) and γP (xφ ) ≤ p(|φ|), and for every unsatisfiable formula φ there exists xφ (encoding unsatisfiability) with γP (xφ ) ≤ p(|φ|). Remark 4.8 (Role of the K condition in Theorem C). The hypothesis K(xw ) = Ω(|w|) in the (⇒) direction is necessary and not vacuous. When K(xw ) ≪ |w|, for instance when the only witness for w is a highly regular string such as 0n , the near-shortest descriptions of xw have length K(xw ) ≪ |w|, and no M ∈ P can produce xw (of length Ω(|w|)) from such a description in poly(K(xw )) ≪ |xw | steps. In this case γP (xw ) = ∞ even under P = NP: the compact encoding of xw is operationally inaccessible, an instance of the separation between descriptive and decompression complexity that is the central theme of this paper. The condition K(xw ) = Ω(|w|) identifies the certificates for which decompressibility and P = NP are equivalent. Under P = NP, such certificates always exist: the algorithm A of Remark 2.7 produces cw in polynomial time, and by a standard counting argument one can always find a witness c′w with K(1, c′w ) = Ω(|w|): append any pad of polynomial length that yields high Kolmogorov complexity (such pads exist by the counting argument, though they need not be computable in polynomial time), without increasing the verifier’s acceptance time. Proof. We prove the general form; the SAT case is the special instance L = SAT. (⇒) Assume P = NP. By the self-reducibility argument (Remark 2.7), for every L ∈ NP there is a polynomial-time algorithm A deciding L and producing a witness cw when w ∈ L. For w ∈ L, we claim there exists a valid witness c′w of length q(|w|) (for a fixed polynomial q with q(|w|) ≥ |cw |) satisfying K(1, c′w ) = Ω(|w|). To see this: the NP verifier for L accepts c′w = cw ∥r for any string r of length q(|w|) − |cw |. By a standard counting argument [11], fewer than 2q(|w|)−c strings of length q(|w|) + 1 have K < q(|w|) − c; hence for all but a 2−c fraction of choices of r, the resulting c′w satisfies K(1, c′w ) ≥ q(|w|) − c = Ω(|w|). Such a c′w exists; fix one for each w (no requirement that the selection be polynomial-time computable from w). Define xw = (1, c′w ) and the description dw = ⟨w, πA ⟩, where πA is the O(1)-bit index of A in U ’s program table. Then |dw | = |w|+O(1). Since K(xw ) = Ω(|w|) by construction and |dw | = |w| + O(1) = O(K(xw )), the description dw satisfies |dw | ≤ K(xw ) + c0 for all sufficiently large |w|, so dw is a near-shortest description of xw . Define the decompressor Mc′w to be the machine that, on input dw = ⟨w, πA ⟩, runs A(w) to obtain cw and then outputs (1, cw ∥r) where r is a fixed string of length q(|w|) − |cw | stored as part of the machine description (so |Mc′w | = O(|r|) = O(|w|) depends on |w|, not on w itself). Since A runs in poly(|w|) steps and r is fixed, Mc′w runs in poly(|w|) steps. However, |Mc′w | is not O(1) but O(|w|); this is admissible because dw is near-shortest and γP (xw ) ≤ TMc′ (dw ) = w poly(|w|) = pL (|w|) for a suitable polynomial pL , which is all the theorem requires. For w∈ / L define xw = (0, 0|w| ); since xw consists almost entirely of zeros, K(xw ) = O(log |w|) (a description of length O(log |w|) encodes |w| and the instruction to output a zero-string of that length). A fixed polynomial-time machine reads any near-shortest description d of xw (of length O(log |w|)) and writes the |w| + 1 output bits in O(|w|) steps, so γP (xw ) = O(|w|). (⇐) Assume the condition holds for L = SAT. By hypothesis, for every φ ∈ SAT there exists xφ = (1, c′φ ) with K(xφ ) = Ω(|φ|) and γP (xφ ) ≤ p(|φ|). The latter means 14

there exists M ∗ ∈ P (fixed, independent of φ) and a near-shortest description d∗ of xφ with M ∗ (d∗ ) = xφ and TM ∗ (d∗ ) ≤ p(|φ|). Since K(xφ ) = Ω(|φ|), the near-shortest description d∗ has length |d∗ | ≤ K(xφ ) + c0 = O(|φ|). Moreover, M ∗ is a fixed polynomial-time algorithm that, given φ, produces xφ ; the natural description is d∗ = ⟨φ, πM ∗ ⟩ where πM ∗ is the O(1)-bit index of M ∗ . Since K(xφ ) = Ω(|φ|), this description is near-shortest: |d∗ | = |φ| + O(1) ≤ K(xφ ) + c0 . The procedure D fixes M ∗ (by trying all O(1) possible machine indices π) and searches only over descriptions of the form ⟨φ, π⟩: there are O(1) such candidates per φ. Running each for at most t = p(|φ|) steps in round-robin gives total time T = O(1) · p(|φ|) = poly(|φ|). Whenever D finds a pair (M, d) producing output z, verify: if z[0] = 1 and the SAT verifier accepts (φ, z[1 :]), report φ ∈ SAT. If no such pair completes within budget T , report φ ∈ / SAT. Correctness: if φ ∈ SAT, the good pair (M ∗ , d∗ ) completes within T and produces a valid certificate, so φ ∈ SAT is reported. If φ ∈ / SAT, no pair can produce a string z with z[0] = 1 passing the verifier (no satisfying assignment exists), so the algorithm correctly reports φ ∈ / SAT. The total time is poly(|φ|), so SAT ∈ P, giving P = NP. The general (⇐) direction follows immediately: P = NP implies polynomial-time solvability of every L ∈ NP. Remark 4.9 (γP as exact discriminant). Theorem 4.7 establishes that the question “is γP polynomially bounded on NP certificates with K(xw ) = Ω(|w|)?” is identical to P = NP rephrased in the language of witness complexity. The K(xw ) = Ω(|w|) condition identifies the certificates for which descriptive and decompression complexity are formally coupled: these are the certificates whose compact encoding is non-trivially short relative to the instance size (Remark 4.8). For certificates with K(xw ) ≪ |w|, γP (xw ) = ∞ unconditionally (Remark 2.7), and the P = NP question does not arise: such certificates are inaccessible via their compact encodings regardless of the P = NP answer. To the authors’ knowledge, no other known characterisation of P = NP (circuit lower bounds, proof complexity, communication complexity) gives an unconditional biconditional in the standard Turing model identifying precisely the class of certificates for which the equivalence holds.

4.4

Theorem B’: Unconditional Lower Bound on γ

Theorem 4.10 (B’ — Unconditional lower bound). Assuming only the classical incomputability of K [11]: for every polynomial p, there exists y ∈ {0, 1}∗ such that γ(y) > p(|y|). Consequently, γ is not polynomially bounded on {0, 1}∗ . Theorem 4.11 (Ganardi–Jeż–Lohrey [6]). Any straight-line program (SLP) of size g generating a string of length N can be transformed in O(g) time into an equivalent SLP of size O(g) and derivation depth O(log N ). Proof sketch. Suppose for contradiction that γ(y) ≤ p(|y|) for every y and some polynomial p. We show this implies K is computable, contradicting its classical incomputability. Given y of length n, enumerate all self-delimiting programs d of length ≤ n + c0 (finitely many, at most 2n+c0 +1 ) and simulate U on each for at most p(n) steps. Under the hypothesis, there exists a near-shortest description d′ achieving γ(y) (i.e. |d′ | ≤ K(y) + c0 and TU (d′ ) = γ(y) ≤ p(n)), so d′ is found in the enumeration and produces y within the 15

budget. The minimum length among all descriptions that produce y within p(n) steps equals K(y) to within c0 . This algorithm terminates for every y and computes K(y) to within c0 , contradicting incomputability. Full proof in Appendix B. Remark 4.12 (Relationship between Theorem B, Theorem B’, and Theorem C). Theorem B’ (unconditional) guarantees superpolynomial γ exists for some string, but does not exhibit which one. Theorem B (conditional on P ̸= NP) exhibits an explicit family. The two are complementary. Combining Theorem B’ with Theorem C does not imply P ̸= NP: the strings with superpolynomial γ guaranteed by Theorem B’ may all lie outside any NP language (e.g. algorithmically random strings with K(y) ≈ |y| have no connection to NP witnesses). Formally: ∀p ∃y : γ(y) > p(|y|) {z } |

is compatible with

∀L ∈ NP, ∀w : γP (xw ) ≤ pL (|w|) | {z } consequence of P=NP via Theorem C

Theorem B’

because the first quantifier ranges over {0, 1}∗ while the second ranges over NP instances. Theorems B’ and C together do not imply P ̸= NP.

4.5

Theorem D: Tractability on Structurally Guided Families

Definition 4.13 (Structurally guided family). A family F of instances of an NP problem L is structurally guided if there exists a polynomial-time procedure PF and a polynomial p such that for every x ∈ F : (1) PF (x) produces a description d with |d| ≤ K(yx ) + c0 where yx is a valid witness for x in L, and (2) there exists a deterministic Turing machine M with M (d) = yx and TM (d) ≤ p(|x|). Condition (1) requires that PF finds a near-shortest description of yx . Condition (2) requires that this same description d can be expanded to yx in time bounded by a polynomial in |x| (the instance size, not the description length). Both conditions on the same d are necessary: (1) without (2) gives a compact description with no efficient decompressor; (2) without (1) gives an efficient decompressor that does not operate on a near-shortest input. Remark 4.14 (Time bound in condition (2)). Condition (2) of Definition 4.13 does not require M ∈ P in the standard sense (polynomial time in |d|). It requires only TM (d) ≤ p(|x|), which can exceed poly(|d|) when |d| ≪ |x|. This is the correct bound for Theorem 4.16: the total time of the resulting algorithm is poly(|x|) regardless of |d|. When K(yx ) = Ω(|x|), the two notions coincide and M is necessarily in P. Remark 4.15 (The same-description requirement). Definition 4.13 requires conditions (1) and (2) to hold for the same description d. This is essential: (1) without (2) yields a compact description with no efficient decompressor; (2) without (1) yields an efficient decompressor that does not operate on a near-shortest input. Only when both conditions are satisfied by the same d does Definition 4.13 guarantee that PF produces a description that is simultaneously compact and efficiently executable.

16

Theorem 4.16 (D — Tractability on structurally guided families). If F is a structurally guided family for L ∈ NP with procedure PF and polynomial p, then L is solvable in polynomial time on F . Proof. Let x ∈ F . Run PF (x) in polynomial time to obtain description d with |d| ≤ K(yx ) + c0 (condition (1)). By condition (2), there exists a deterministic Turing machine M with M (d) = yx and TM (d) ≤ p(|x|). Run M (d) in time ≤ p(|x|) to obtain yx . Verify yx using the NP verifier for L in polynomial time. If verification succeeds, output yx and accept. Total time: poly(|x|). Correctness: M (d) = yx by condition (2), and the verifier accepts yx because yx is a valid witness for x ∈ F ⊆ L. Remark 4.17 (Relation to Theorem C and unconditional status). Theorem 4.7 characterises P = NP as the existence of polynomially bounded γP (with M ∈ P, i.e. time polynomial in |d|) for KC-rich certificates across all NP instances. Theorem 4.16 is local and unconditional: it applies to a specific structurally guided family F and requires no complexity-theoretic hypothesis. The time bound in Theorem 4.16 is p(|x|) (polynomial in the instance size), which may exceed poly(|d|) when K(yx ) ≪ |x| (Remark 4.14); this is the reason Theorem 4.16 can hold unconditionally even when K(yx ) ≪ |yx |, a regime where γP (yx ) = ∞ in the strict sense of Definition 2.6.

4.6

Conjecture: Uniform Witness Representation

Conjecture 4.18 (Uniform witness representation). For every L ∈ NP, there exists a polynomial-time computable function fL : w 7→ xw such that K(fL (w)) = Ω(|w|) and γP (fL (w)) ≤ pL (|w|) for a fixed polynomial pL , uniformly across all w ∈ L. The distinction from Theorem 4.7 is uniformity: the (⇒) direction of Theorem 4.7 establishes, for each instance w separately, the existence of a KC-rich certificate xw with γP (xw ) ≤ pL (|w|), but the choice of xw is existential and not required to be polynomialtime computable from w. Conjecture 4.18 requires a uniform polynomial-time map w 7→ xw satisfying both the K and γP conditions. Whether this is equivalent to, strictly stronger than, or independent of P = NP is open; see Question Q1 in Section 9.

5

Separation Examples

This section exhibits three families of strings that witness the following separations: low K does not imply low γ (Example 5.2), low K does not imply polynomial γP (Example 5.1, conditional), and high K forces γ to the same asymptotic order as K (Example 5.3). All examples are unconditional except Example 5.1, which requires P ̸= NP. Example 5.1 (Low K, high γP : the SAT-witness family). Hypothesis: P ̸= NP. Construction: the family {xφ } of Theorem 4.4 (Definition in the proof of Theorem 4.4, Section 4.2). For each formula φ on n variables: ( (1, yφ ) if φ ∈ SAT, where yφ is the lex-first satisfying assignment, xφ = (0, 0n ) if φ ∈ / SAT. Verification: 17

(i) K(xφ ) = O(|φ|): the near-shortest description dφ = ⟨φ, π⟩ has length |φ| + O(1), witnessing K(xφ ) ≤ |φ| + O(1). (ii) γP (xφ ) is superpolynomial in |φ| for all φ in the infinite subfamily Fc0 : by Theorem 4.4, any polynomial-time decompressor for xφ from a near-shortest description would solve SAT in polynomial time, contradicting P ̸= NP. Separation exhibited : K(xφ ) = O(|φ|) and γP (xφ ) superpolynomial. Short description, computationally inaccessible content. Cryptographic interpretation: these are compact witnesses whose recovery cost exceeds any polynomial budget. A protocol that stores xφ as dφ and expects polynomial-time recovery cannot function under P ̸= NP. Example 5.2 (Low K, moderate γ: PRNG expansion). Construction: let G : {0, 1}k → {0, 1}n be a pseudorandom generator with seed length k ≪ n, running in time TG ≤ β · n for a fixed constant β. Let s ∈ {0, 1}k be an incompressible seed (K(s) ≥ k − c0 ) and set x = G(s). Verification: (i) K(x) ≤ K(s) + O(1) ≤ k + O(1): given s, a constant-length instruction suffices to run G and produce x. Since k ≪ n, we have K(x) ≪ n = |x|. (ii) γ(x) ≥ n: any Turing machine that produces n bits of output must perform at least n write steps (one per output bit), so every near-shortest description of x requires at least n steps to execute. (This elementary lower bound is independent of Proposition 3.1, which gives only γ(x) ≥ K(x) = O(k) ≪ n here.) (iii) γ(x) ≤ TG = β · n: the description ⟨s, πG ⟩ has length k + O(1) ≤ K(x) + c0 (nearshortest, since K(x) ≤ k + O(1)), and U on this description runs G(s) in at most β · n steps. Therefore γ(x) = Θ(n), while K(x) = O(k) ≪ n. Separation exhibited : K(x) = O(k) and γ(x) = Θ(n). The gap γ(x)/K(x) = Θ(n/k) is unbounded when k = O(log n). Cryptographic interpretation: this is the key-expansion scenario. The seed is the compact key; x is the keystream. The expansion cost γ(x) = Θ(n) is unavoidable: n bits must be produced. Example 5.3 (High K, γ ≈ K: algorithmically random string). Construction: let x ∈ {0, 1}n satisfy K(x) ≥ n − c0 (incompressible; all but at most a 2−c0 fraction of strings of length n have this property, by the standard counting argument: fewer than 2n−c0 programs of length < n − c0 exist, so at most 2n−c0 strings of length n can have K(x) < n − c0 ). Verification: (i) K(x) ≤ n + O(1): the identity description has length n + O(1). Together with K(x) ≥ n − c0 , this gives K(x) = Θ(n). (ii) γ(x) ≥ K(x) = Θ(n): by Proposition 3.1. (iii) γ(x) ≤ n + O(1): by Proposition 3.5. 18

Therefore γ(x) = Θ(n) = Θ(K(x)). Separation exhibited : for incompressible strings, K and γ coincide up to constant factors. No gap exists. Cryptographic interpretation: incompressible strings cannot be stored more compactly than their raw form. They are not useful as compressed keys because K(x) ≈ |x| — no compact representation exists. Remark 5.4 (Summary: independence of K and γ). The three examples confirm that K(x) and γ(x) are provably independent: • Low K, high γP (Example 5.1, conditional): a compact description can be computationally inaccessible. • Low K, moderate γ (Example 5.2, unconditional): a compact description can require linear work to expand, without any complexity-theoretic hardness. • High K, γ ≈ K (Example 5.3, unconditional): no compact description exists, and decompression cost matches information content. The relevant quantity for cryptographic usability is γP , not K alone.

6

Discussion and Related Work

6.1

Relation to prior complexity measures

Levin’s Kt complexity. Levin’s Kt(x) = mind {|d| + log TU (d) : U (d) = x} combines description length and log-running-time into a single quantity [10, 11]. The quantity γ(x) differs in two respects: it fixes the length constraint to near-minimal and minimises running time directly, and the minimisation is over a set of near-shortest descriptions rather than a single weighted trade-off. The spectrum K −→ K t −→ Kt −→ γ represents increasing sensitivity to computational cost (illustratively, not as a formal ordering for all strings): K ignores cost entirely; K t caps it at a fixed bound t; Kt penalises it logarithmically; γ minimises it directly subject to the near-shortest constraint. To the authors’ knowledge, γ has not been studied as a standalone invariant prior to this work. Time-bounded Kolmogorov complexity K t . K t (x) = min{|d| : U (d) = x in ≤ t steps} fixes a time bound and minimises description length; γ fixes the length constraint and minimises time. The two questions are dual in direction: K t asks “how short can the description be if we cap the time?”; γ asks “how fast can we decompress if we insist on a near-shortest description?” A formal quantitative relation between γ and K t is an open problem; see Question Q5 in Section 9. Proof complexity. Proof complexity measures the minimum cost of verifying or finding a proof of a statement. γ(x) satisfies γ(x) ≥ K(x) (Proposition 3.1): description length lower bounds decompression time. An analogous bound relating proof complexity measures to description length has not been established; formalising this connection is an open problem. 19

Distinguishing γ from related notions. The quantity γ differs from computational depth [11] in that depth measures the time to compute x from the empty string (no short description assumed), while γ measures the time to decompress from a near-shortest description. It differs from sophistication [11] in that sophistication measures the twopart description complexity (model plus data), while γ fixes the near-shortest constraint and minimises decompression time. Formalising the relationships between γ and these notions is an open problem listed in Section 9.

6.2

Applications

Industrial SAT. Modern Conflict-Driven Clause Learning (CDCL) solvers succeed on industrial instances (hardware verification, planning) that may have millions of variables. The γ framework provides a structural explanation: if industrial instances have solutions yφ with low K(yφ ) and a near-shortest description that is efficiently expandable, then Theorem D guarantees polynomial-time solvability on those families unconditionally. For random instances near the phase transition, empirical solving times are superpolynomial; this is consistent with Theorem B (conditional on P ̸= NP), which establishes the existence of compact witnesses with superpolynomial γP in the SAT-witness family {xφ }. Whether γP growth tracks the phase transition in random SAT is an open question (Question Q2 in Section 9). Machine learning. Training a neural network can be interpreted as searching for a decompressor M ∈ H (over a hypothesis class H) that minimises γP over the training distribution: the learned model is a decompressor, and training searches for M that reconstructs the data distribution from a compact latent representation. This is an interpretive reframing; formal connections to VC dimension, PAC-Bayes bounds, or MDL require additional work and are listed as Question Q3 in Section 9. We do not claim any quantitative results in this direction. Coding theory. An error-correcting code with compact structure (low K for the code description) and efficient decoding (low decompression cost from received words) corresponds to low γ for its codewords in the decompressor regime. This analogy is approximate: received words may not be near-shortest descriptions of codewords, so γ does not directly apply. We conjecture that γ could serve as a benchmark for comparing the computational accessibility of different code families; formalising this connection is left for future work.

6.3

Efficiency ratios

Definition 6.1 (Efficiency ratio). For an algorithm A and input x producing output y = A(x), with γ(y) > 0 (guaranteed by Proposition 3.1 for non-empty y): η(A, x) =

TA (x) , γ(y)

ηP (A, x) =

TA (x) γP (y)

(where ηP is defined only when γP (y) < ∞). The ratio η(A, x) is well-defined since γ(y) ≥ K(y) > 0 for every non-empty y (Proposition 3.1 and hypothesis (H3)). It is non-effective since γ is not computable (it cannot 20

be computed by any Turing machine, by Theorem B’). It serves as a theoretical benchmark: η(A, x) = 1 means A achieves the minimum decompression time on input x. The class-relative ratio ηP is estimable by exhibiting any concrete M ∈ P that reconstructs y from a near-shortest description, giving an upper bound on γP (y) and hence a lower bound on ηP .

7

Threat Model and Cryptographic Implications

This section formalises the cryptographic threat model sketched in Section 1.1 and derives concrete implications of Theorems A–D for protocol design.

7.1

Assets, adversary, and relevant metrics

Assets. The primary assets are compact representations (near-shortest descriptions) of keys, certificates, and witnesses, together with their decompressed outputs. Adversary model. We consider adversaries with polynomial or superpolynomial computational resources, capable of: • submitting crafted compact descriptions and triggering decompression (active); • observing decompression cost and timing (passive); • inducing desynchronisation of session state (disruptive). We do not formalise a full cryptographic security definition (e.g. indistinguishability or semantic security); such a definition would require a probability distribution over keys and an explicit model of adversarial access. The analysis here is usability-based : we ask whether a compact representation can be expanded within a bounded time budget, not whether it is computationally indistinguishable from random. Relevant metrics. The theoretical metric is γP (x) (Definition 2.6) and its class-relative variants. Practical proxies include empirical decompression time Tdec , compressor output size (LZ/SLP), and derivation depth. Since K is not computable [11], practical approximations are necessary.

7.2

Implications of the main theorems

Theorem A (Invariance). The polynomial invariance of γ across universal machines (Theorem 4.2) guarantees that the property of γP (x) being polynomially bounded is machine-independent: if γP (x) ≤ p(|x|) with respect to one universal machine, then γP (x) ≤ q(|x|) · p(|x|) + O(1) with respect to any other, for a polynomial q depending only on the pair of machines (not on x). The specific bound p changes across machines, but the qualitative property (existence of a polynomial bound) does not. This is a prerequisite for any machine-independent security argument based on γ.

21

Theorem B (Conditional separation). Under P ̸= NP, there exist compact witnesses x with K(x) = O(|x|) and γP (x) superpolynomial. A protocol that stores such an x as a near-shortest description d and expects polynomial-time recovery will fail: no polynomial-time decompressor can reconstruct x from d. Consequence for short-key protocols: if a key generation algorithm produces keys as near-shortest descriptions of their expanded form, and if the expansion problem is NPhard, then P ̸= NP implies that some keys cannot be expanded in polynomial time. Protocol designers must either (a) verify that the specific key family has polynomial γP (e.g. by exhibiting an explicit decompressor), or (b) avoid relying on compact representations of NP-hard objects. Theorem C (Exact characterisation). γP is polynomially bounded on NP certificates with K(xw ) = Ω(|w|) if and only if P = NP (Theorem 4.7, Remark 4.8). The question of whether a compact certificate scheme is usable for KC-rich certificates (polynomial decompression when the certificate’s Kolmogorov complexity is commensurate with the instance size) is therefore logically equivalent to P = NP: any answer to the usability question immediately yields an answer to P vs NP, and vice versa. For KC-poor certificates (K(xw ) ≪ |w|), γP (xw ) = ∞ unconditionally: their compact encodings are operationally inaccessible regardless of the P = NP answer. Theorem D (Tractability on structured families). For structurally guided families (Definition 4.13), polynomial-time decompression is unconditionally guaranteed (Theorem 4.16). This provides a sufficient condition for usability that does not depend on P vs NP: if a key or certificate family admits a polynomial-time procedure that finds a nearshortest description and a decompressor running in time polynomial in the instance size (Definition 4.13, condition (2)), then decompression is efficient.

7.3

Attack scenarios

DoS via expensive decompression. An adversary submits compact descriptions d of strings x = U (d) with large γP (x) to a verifier that decompresses before checking. If the verifier runs without a time budget, the adversary saturates it. Mitigation: enforce a polynomial time budget p(|d|) on decompression; reject any d that exceeds it. Theorem A guarantees that the time budget is machine-independent. Key-usability attack. A compact key d encoding a string x = U (d) with γP (x) superpolynomial cannot be expanded in polynomial time; an adversary can exploit this to cause key-derivation failures or timing attacks. Mitigation: certify that the key family is structurally guided (Theorem D) before deployment. Desynchronisation. In protocols where both parties hold a near-shortest description of a shared state and must expand it synchronously, an adversary inducing message loss can desynchronise the parties. If re-synchronisation requires re-expanding the state from scratch and γP is large, this causes a denial-of-service. Mitigation: design protocols to carry explicit state rather than relying on re-derivation from compact encodings when γP is not certifiably polynomial. Remark 7.1 (Limits of the framework). The γ framework measures usability (decompression cost), not security (computational indistinguishability or hardness of inversion). A 22

key k with low γP (k) can be efficiently reconstructed from its compact description, but this says nothing about whether an adversary who does not hold the description can find k. Security and usability are orthogonal properties; both are necessary for a cryptographic primitive to be deployed in practice.

8

Application: Grammar-Based Compression

Grammar-based compression provides the cleanest formal setting in which to exhibit a descriptive-vs-decompression-cost gap unconditionally, without any hypothesis on P = NP. The gap is between grammar size g ∗ (x) (the grammar-theoretic analogue of K(x)) and derivation cost γCFG (x) (the grammar-theoretic analogue of γ(x)): among all nearminimal grammars for a string x, the derivation cost can vary by a super-constant factor invisible to any measure depending only on grammar size.

8.1

Background: the Smallest Grammar Problem

The Smallest Grammar Problem (SGP) asks: given a string x, find the smallest contextfree grammar G such that L(G) = {x}. The SGP is NP-hard [3]: no polynomial-time algorithm computes a smallest grammar unless P = NP. The literature on grammarbased compression (LZ78 [15], SEQUITUR [13], RE-PAIR [9]) focuses on grammar size |G| as the sole measure of compression quality. No existing measure distinguishes between a smallest grammar with low derivation cost and one that is expensive to expand despite being size-minimal.

8.2

Grammar witness complexity

Definition 8.1 (Grammar witness complexity). For a string x ∈ {0, 1}∗ , let g ∗ (x) denote the size (number of production rules) of the smallest context-free grammar G with L(G) = {x}. The grammar witness complexity of x is γCFG (x) =

min

G : L(G)={x}, |G|≤g ∗ (x)+cg

Tderive (G),

where Tderive (G) is the number of steps required to expand G to x via its derivation, and cg is a fixed constant depending only on the grammar model (analogous to c0 in hypothesis (H1) for Kolmogorov complexity, but specific to the grammar-size measure). The minimisation is over all near-minimal grammars for x; among these, γCFG (x) is the minimum derivation cost. Instance of the general framework : this is Definition 2.6 with descriptions being grammar rules, description length being grammar size, and decompression being the derivation of G to produce x. Cryptographic interpretation: d is a near-minimal grammar G; U (d) = x is the derivation step; Tderive (G) is the cost of recovering x from its compressed representation G. γCFG (x) is the minimum recovery cost over all near-minimal compressed representations.

8.3

The gap lemma

The key result of this section is that γCFG (x) can be much smaller than the derivation cost of the natural minimal grammar, unconditionally. 23

Lemma 8.2 (Grammar complexity gap). There exist strings x of length N = Θ(n2 ) such that: √ (i) The smallest grammar G∗ for x satisfies g ∗ (x) = |G∗ | = Θ(n) = Θ( N ). √ (ii) The natural minimal grammar G∗ has derivation depth Tderive (G∗ ) = Ω(n) = Ω( N ). (iii) There exists a grammar G′ with |G′ | = O(|G∗ |) (near-minimal) and Tderive (G′ ) = O(log N ). Parts (ii) and (iii) together show that among √ near-minimal grammars for x, derivation depth varies by a factor of Θ(n/ log n) = Θ( N / log N ), a gap invisible to any measure depending only on grammar size. √ In particular, γCFG (x) = O(log N ) while the natural minimal grammar has depth Ω( N ). Proof sketch. Construction. Throughout this proof we work over the two-symbol alphabet {a, b} (which can be identified with {0, 1} via a 7→ 0, b 7→ 1; the blocks ai then become runs of zeros). Let n ≥ 1 and define x = a1 b a2 b · · · an b, so |x| = N =

2 ∗ i=1 (i + 1) = n(n + 1)/2 + n = Θ(n ). Consider the natural grammar G :

Pn

S → A1 B1 , Bi → b Ai+1 Bi+1 (1 ≤ i < n), Ai → a Ai−1 (i ≥ 1), A0 → ε.

Bn → b,

Proof of (i). The grammar G∗ has O(n) rules. For optimality: x contains n blocks a , a2 , . . . , an of pairwise distinct lengths; any grammar distinguishing √ all blocks requires ∗ ∗ Ω(n) non-terminals, so g (x) = Ω(n). Together: g (x) = Θ(n) = Θ( N ). Proof of (ii). To derive the block ai , the non-terminal Ai must expand Ai−1 , which expands A √i−2 , down to A0 : a derivation chain of depth i. The maximum over all blocks is n = Ω( N ). Proof of (iii). By Theorem 4.11 (stated before this proof), applying to G∗ (which is an SLP of size Θ(n) generating x of length N = Θ(n2 )) yields a grammar G′ with |G′ | = O(n) = O(|G∗ |) and Tderive (G′ ) = O(log N ). Full details in Appendix A.1 1

Remark 8.3 (Unconditional nature of the gap). Lemma 8.2 does not involve P = NP: the constructions are explicit and the bounds elementary (the lower bound in (ii) is a direct chain-depth argument; the upper bound in (iii) cites an unconditional algorithmic result [6]). The structure is conceptually identical to Theorem 4.4: descriptive complexity (g ∗ , resp. K) is low while decompression complexity (γCFG , resp. γP ) varies. The SGP instance makes the separation unconditional and explicit. Remark 8.4 (Implication for grammar-based compression systems). All existing grammarbased compression systems (LZ78 [15], SEQUITUR [13], RE-PAIR [9]) minimise grammar size and are therefore blind to the derivation-cost gap exhibited by Lemma 8.2. If a compressed object is stored as a near-minimal grammar and must be decompressed under a time budget, the natural minimal grammar may be unusable while a balanced equivalent grammar (of the same asymptotic size) is efficiently derivable in O(log N ) depth. In cryptographic terms: two compressed keys stored √ as near-minimal grammars of the same size can have derivation costs differing by Θ( N / log N ). A protocol that enforces a time budget must therefore specify not merely that the grammar is near-minimal, but that it is balanced in the sense of Theorem 4.11. The full proof verifies that the transformation of Theorem 4.11 preserves the property L(G′ ) = {x} and that |G′ | remains within the near-minimal bound g ∗ (x) + cg . 1

24

9

Open Questions

We list seven open questions arising from the framework developed in this paper. Each is stated with precise hypotheses and a note on what the paper does and does not resolve. Q1. Status of the Uniform Witness Conjecture (Conjecture 4.18) relative to P = NP. The conjecture asks: for every L ∈ NP, does there exist a polynomial-time computable function fL : w 7→ xw with K(fL (w)) = Ω(|w|) and γP (fL (w)) ≤ pL (|w|) uniformly? What the paper resolves: under P = NP, the (⇒) direction of Theorem 4.7 guarantees that KC-rich certificates with γP ≤ pL (|w|) exist for every w ∈ L, but their selection is existential, not polynomial-time computable from w. Under P ̸= NP, the conjecture is false for SAT by Theorem 4.4 (the family Fc0 satisfies K(xφ ) = Ω(|φ|) but γP is superpolynomial). What remains open: could the conjecture hold for some L ∈ NP strictly easier than SAT (e.g. graph 2-colouring or bipartite matching), even under P ̸= NP? If so, the conjecture would not be equivalent to P = NP but would instead characterise a finer structural property of L. The precise relationship — equivalent to P = NP, strictly stronger than the conjecture for a specific L, or independent of P = NP for easy NP problems — is not settled by the results of this paper. Q2. Phase transitions in random SAT and γP . Do empirical phase transitions in random SAT (near the conjectured threshold of approximately 4.267 clause-to-variable ratio for 3-SAT [7]) correspond to rapid growth in γP of the SAT-witness family {xφ } as a function of instance structure? Theorem 4.4 establishes superpolynomial γP for the explicit family Fc0 under P ̸= NP, but says nothing directly about random instances. Whether γP growth tracks the phase transition is an open problem. Q3. Formal correspondence between γP and generalisation bounds. Is there a formal correspondence between minimising γP over a hypothesis class H and existing generalisation bounds (VC dimension, PAC-Bayes, or MDL)? The interpretive reframing in Section 6 motivates this question but does not yield quantitative results; we conjecture that such a correspondence exists. Q4. Quasi-linear invariance of γ. The polynomial invariance of Theorem 4.2 involves a factor q(|x|) = CC ·|x|kC where kC is the degree of the simulation overhead. Can the invariance be tightened — for instance to a quasi-linear factor O(|x| log |x|) — for natural subclasses of universal machines (e.g. RAM-based or oblivious Turing machines)? The constants CC and kC in Lemma 4.1 can in principle be made explicit; whether they are tight for specific machine models is open. Q5. Quantitative relation between γ and K t . The definitions of γ and K t are dual: K t fixes time and minimises length; γ fixes near-minimal length and minimises time. Is there a quantitative relation of the form γ(x) ≤ f (K t (x), t) for some explicit f , where t ranges over values such as t = γ(x) (relating the two quantities at the same operating point) or t = poly(|x|) (in the polynomial regime)? Conversely, does K t (x) ≤ g(γ(x)) hold for some explicit g and appropriate t? A complete characterisation of the trade-off between these two quantities would clarify the structure of the spectrum K → K t → Kt → γ (Remark 2.9). Q6. Structure of sub-level sets of γ.

25

Define the t-sub-level set of γ as Λt = {x ∈ {0, 1}∗ : γ(x) ≤ t}. What is |Λt ∩ {0, 1}n | as a function of n and t? When Λt is large (many strings of length n have γ ≤ t), the nearshortest descriptions achieving cost ≤ t cover many outputs; understanding this density characterises how much information a budget-t decompressor can retrieve. The density of Λt may be related to the entropy of source distributions for which budget-bounded decompression is efficient. Q7. Relation between γCFG and γ. Lemma 8.2 exhibits a gap between grammar size g ∗ (x) and derivation cost γCFG (x). What is the quantitative relation between γCFG (x) and γ(x)? Since γCFG uses grammars as descriptions while γ uses self-delimiting programs for U , the two quantities measure different aspects of decompression cost. In particular: is there a family of strings for which γ(x) ≪ γCFG (x) or γCFG (x) ≪ γ(x)?

What Part I Establishes The five results of Part I are not independent contributions but a single coherent argument. Theorem A is a prerequisite: without machine independence, neither Theorem C nor any other complexity-theoretic application of γ would be well-founded. Theorems B and B’ delimit the framework from below: they establish that γP is not trivially bounded, neither on a specific explicit family (conditionally) nor anywhere on {0, 1}∗ (unconditionally). Theorem C is the central claim: γP is the discriminant of P = NP among certificates with K(xw ) = Ω(|w|), in the standard Turing model and with no auxiliary hypothesis. For KC-poor certificates, γP = ∞ unconditionally — a phenomenon the framework identifies as constrained inaccessibility rather than a limitation of Theorem C. Theorem D shows that the framework is not merely a restatement of the open problem: for structured families, polynomial-time decompressibility is provable unconditionally, without assuming P = NP. Together, the five results answer the question of Section 1.1 at the right level of generality: γP separates compact representations that are operationally accessible from those that are not. For KC-rich certificates (K(xw ) = Ω(|w|)), that condition is equivalent to P = NP (Theorem C). For KC-poor certificates, γP = ∞ unconditionally, identifying a distinct form of inaccessibility independent of P = NP. In the structured cases that arise in practice (Theorem D), polynomial-time accessibility is provable without any complexity assumption.

Part II: Adaptive Complexity, Computational Overhead, and Structural Entropy Part I asked a single question about an object x: given that a near-shortest description of x exists, how much work is required to execute it? The answer is γ(x), or γP (x) when the decompressor is restricted to P. This question is object-intrinsic: it concerns x independently of how it was produced or how it will be used. Three related but distinct questions fall outside its scope. 26

The first concerns the input side of a computation, not its output. Running time is measured against input length n = |x|, treating all inputs of the same length identically regardless of their actual information content K(x). When K(x) ≪ n, an algorithm may spend most of its steps on structure already implicit in x; Tad (A, x) = TA (x)/K(x) (Section 10) measures work per bit of input information, making this cost explicit. The second concerns the output side. Any algorithm producing output of length m must spend at least m steps writing it; the computationally meaningful quantity is the overhead beyond this unavoidable minimum. OCout (A, x) = TA (x) − |A(x)| (Section 11) isolates this overhead from the bare cost of writing the output. The third concerns the structure of solutions. γP (x) being polynomially bounded characterises the decompressibility of x, but says nothing about how much information the witness yx itself carries. Hs (y) = K(y)/ log2 |y| (Section 12) measures the information density of yx : whether solutions to structured instances are more compressible than those of random instances of the same size. The three quantities are orthogonal to γ: they do not extend it but measure aspects of algorithmic cost and solution structure that γ and γP , by design, leave unaddressed.

10

Adaptive Complexity

Standard complexity measures algorithm cost as a function of input length n = |x|, treating all inputs of the same length identically regardless of their information content. An algorithm running in O(n log n) time is considered efficient whether x carries n log n bits of genuine information or is 99% redundant. Adaptive complexity corrects this by normalising running time by the actual information content of the input. Definition 10.1 (Adaptive complexity). For an algorithm A and input x with K(x) ≥ 1, the adaptive complexity of A on x is Tad (A, x) =

TA (x) . K(x)

K(x) is not computable in general, so Tad is a non-effective theoretical measure in the same sense as γ. Practical approximations — time-bounded K t (x), class-relative KP (x), or compressor-based proxies such as the LZ77 output length — can replace K(x) in applications. Cryptographic interpretation: Tad (A, x) measures the work per bit of genuine information in x. An algorithm with Tad (A, x) = O(1) is information-optimally efficient: it does a constant amount of work per bit of genuine input content. An algorithm with Tad (A, x) ≫ 1 wastes work on structure that was already implicit in x. Remark 10.2 (Well-definedness). The condition K(x) ≥ 1 is guaranteed for every nonempty x by hypothesis (H3). For x = ε, Tad is undefined; all results below assume x ̸= ε. The following lemma (Lemma 10.3) illustrates Tad concretely by computing it for comparison-based sorting, showing that Tad ≥ 1 on incompressible permutations. Lemma 10.3 (Instance-sensitive lower bound for sorting). Let A be any comparison-based sorting algorithm and x a permutation of [n] = {1, . . . , n}. Let RA (x) denote the number of permutations of [n] that are indistinguishable from x by A, i.e. that share the same decision-tree leaf as x. In the comparison model (where each comparison costs O(1)): TA (x) ≥ log2 27

n! . RA (x)

For incompressible permutations x with K(x) ≥ log2 n! − c0 , this gives TA (x) ≥ K(x) − O(1) and hence Tad (A, x) ≥ 1 − O(1/K(x)). In the multi-tape Turing model of hypothesis (H2), each comparison requires O(log n) steps (to read two elements of the permutation array), so the bound becomes TA (x) = Ω(K(x) · log n/ log n) = Ω(K(x)); the conclusion Tad (A, x) ≥ 1 − O(1/K(x)) holds in either model up to logarithmic factors. Proof. Decision-tree lower bound. Algorithm A must perform at least log2 (n!/RA (x)) comparisons to distinguish x from the RA (x) permutations sharing its leaf. This is the standard information-theoretic lower bound for comparison-based sorting [12, 5]. Incompressible case. For x with K(x) ≥ log2 n! − c0 , the leaf containing x in A’s decision tree must distinguish x from all but RA (x) permutations. Since K(x) is near-maximal among permutations of [n] (the maximum is log2 n! + O(log n)), x is not compressible by any short program, so the leaf cannot carry much redundant structure: log2 (n!/RA (x)) ≥ K(x) − O(1). Dividing by K(x) ≥ 1 gives Tad (A, x) ≥ 1 − O(1/K(x)). Remark 10.4 (Scope of the lower bound). The bound TA (x) ≥ log2 (n!/RA (x)) holds for all permutations and all comparison-based algorithms unconditionally. The stronger bound TA (x) ≥ K(x)−O(1) is restricted to incompressible permutations: for highly compressible x (e.g. the identity permutation with K(x) = O(log n)), RA (x) may be 1 and the first bound is tight while the second is vacuous. The framework does not claim a uniform lower bound in K(x) across all inputs.

11

Output Overhead Complexity

Definition 11.1 (Output overhead complexity). For an algorithm A on input x producing output y = A(x), the output overhead complexity is OCout (A, x) = TA (x) − |A(x)|. Proposition 11.2 (Non-negativity). OCout (A, x) ≥ 0 for all A and x. Proof. Algorithm A must write A(x) as output, requiring at least |A(x)| steps (one step per output bit in the standard multi-tape Turing model, where each write to the output tape costs one step). Therefore TA (x) ≥ |A(x)|. Remark 11.3 (Decompressor regime). When A operates in the decompressor regime — that is, when |x| ≤ K(A(x)) + c0 so that x is a near-shortest description of y = A(x) — the machine A is itself a decompressor in the sense of Definition 2.6. Let dA,x denote the self-delimiting description “run A on x”, of length |A| + |x| + O(1). Since |x| ≤ K(y) + c0 , the string dA,x is a near-shortest description of y (up to the constant |A| = O(1) for the fixed machine A). By Theorem 4.2, U simulates A with polynomial overhead: γ(y) ≤ TU (dA,x ) ≤ poly(|x|) · TA (x). Therefore TA (x) ≥ γ(y)/poly(|x|), giving a lower bound on OCout (A, x) + |y|. Outside the decompressor regime (when x is long and redundant relative to y), no such lower bound applies. Definition 11.4 (Decompressor efficiency ratio). For an algorithm A in the decompressor regime producing output y = A(x): ρ(A, x) = 28

TA (x) . γ(y)

By Remark 11.3, ρ(A, x) ≥ 1/poly(|x|). When A is an optimal decompressor, ρ(A, x) = O(1). Example 11.5 (Decompressor efficiency ratio: PRNG). Let G : {0, 1}k → {0, 1}n be a pseudorandom generator. In the decompressor regime, algorithm A receives as input a near-shortest description of the expanded string; here that description is the seed s ∈ {0, 1}k , and A outputs y = G(s) in time TG ≤ βn. By Example 5.2, γ(y) = Θ(n). Therefore TG TA (s) = = O(1). ρ(A, s) = γ(y) Θ(n) The PRNG achieves ρ = O(1): it is optimal in the sense of Definition 11.4, performing within a constant factor of the minimum decompression cost γ(y).

12

Structural Entropy

Definition 12.1 (Structural entropy). For a string y ∈ {0, 1}∗ with |y| ≥ 2, the structural entropy of y is K(y) Hs (y) = . log2 |y| Hs (y) measures the information density of y relative to its size: how compressible y is relative to a logarithmic baseline. Hs ranges from O(1) (highly structured: K(y) = O(log |y|)) to Θ(|y|/ log |y|) (random: K(y) = Θ(|y|)). Cryptographic interpretation: Hs (y) low means y has a compact description; Hs (y) high means y is informationally dense. Low Hs is a necessary condition for y to benefit from compressed storage, but not sufficient for efficient decompression (Proposition 12.3(ii)): low Hs and low γP are both required for a solution to be compactly stored and efficiently recovered. Proposition 12.2 (Basic properties of Hs ). (i) Hs (y) ≥ 0 for all y with |y| ≥ 2. For incompressible strings with K(y) = Θ(|y|): Hs (y) = Θ(|y|/ log |y|) → ∞ as |y| → ∞. (ii) (Standard counting argument; see [11], Theorem 2.2.1.) For a uniformly random string y of length n and every constant c > 0, the probability that K(y) ≥ n − c is at least 1 − 2−c . In particular Hs (y) → n/ log n as n → ∞ for all but a o(1) fraction of strings. (iii) For a string with period p ≤ log n: K(y) = O(p+log n) = O(log n), so Hs (y) = O(1). Proof. (i) K(y) ≥ 0, so Hs (y) ≥ 0. For incompressible y: K(y) ≥ |y| − O(1), so Hs (y) = K(y)/ log |y| ≥ (|y| − O(1))/ log |y| = Θ(|y|/ log |y|). P (ii) A counting argument: there are 2n strings of length n but only i<n−c 2i < 2n−c self-delimiting programs of length < n − c, so at most 2n−c strings have K(y) < n − c. The probability that a uniformly random y satisfies K(y) < n − c is at most 2−c . (iii) A string with period p is determined by its period (a string of length p) and its total length n (encoded in O(log n) bits), so K(y) ≤ p + O(log n) = O(log n) when p ≤ log n. Proposition 12.3 (Hs and γ: demonstrated separations). The following separations hold: 29

(i) (Unconditional.) Hs (y) = O(1) does not imply γ(y) = O(K(y)): there exist strings with low information density whose decompression cost far exceeds their description length. (ii) (Unconditional.) Hs (y) = O(1) does not imply γP (y) < ∞: low information density is not sufficient for polynomial-time decompression. Whether Hs (y) = O(1) implies γ(y) = O(poly(|y|)) is open. The converse direction — whether large γ forces large Hs — is also open; see the proof below. Proof. Part (i), unconditional. The string x = 0n has K(x) = O(log n), Hs (x) = O(1), and γ(x) = Θ(n) (Example 2.3(ii)). Since γ(x) = Θ(n) ≫ O(log n) = O(K(x)), low Hs does not imply γ = O(K). Note that γ(0n ) = Θ(n) remains polynomially bounded; whether low Hs implies polynomially bounded γ is an open problem. Part (ii), unconditional. Let k ≥ 1 be a parameter and let G : {0, 1}k → {0, 1}n be a 2 pseudorandom generator with seed length k and output length n = 2k . Let x = G(s) for an incompressible seed s with K(s) ≥ k − c0 (Example 2.8(iii)). (a) K(x) ≤ K(s)+O(1) ≤ k+O(1), and log |x| = log n = k 2 , so Hs (x) = K(x)/ log |x| ≤ (k + O(1))/k 2 = O(1/k) = O(1). (b) n = 2k is superpolynomial in k: for every constant c, k c < 2k for all sufficiently large k. No polynomial-time machine with input of length k can write n output bits, so γP (x) = ∞ (Example 2.8(iii)). 2

2

(c) γ(x) = Θ(n), finite and polynomially bounded in n (Example 5.2). This is consistent with Remark 3.8: γ(x) is finite while γP (x) = ∞, achieved by a nonpolynomial decompressor. Therefore Hs (x) = O(1) and γP (x) = ∞, unconditionally. Converse direction (open): whether large γ forces large Hs is not known. For incompressible x with K(x) = Θ(|x|), both Hs (x) = Θ(|x|/ log |x|) and γ(x) = Θ(|x|) are large (Example 5.3), but this does not rule out strings with low γ and high Hs . Remark 12.4 (Asymmetry between parts (i) and (ii)). Parts (i) and (ii) of Proposition 12.3 exhibit an asymmetry worth noting. Part (i) shows that Hs (x) = O(1) is compatible with γ(x) = Θ(n), which is polynomially bounded in |x|. Part (ii) shows that the same condition Hs (x) = O(1) is compatible with γP (x) = ∞: the PRNG example of part (ii), combined with Example 5.2, gives simultaneously γ(x) = Θ(n) (finite and polynomially bounded) and γP (x) = ∞ (no polynomial-time decompressor exists). This is consistent with Remark 3.8: γ(x) is achieved by a non-polynomial decompressor, while γP (x) = ∞ because no polynomial-time decompressor can reconstruct x from a near-shortest description. Together, the two parts show that Hs captures neither γ nor γP : low information density is compatible with any combination of finite or infinite decompression cost, depending on whether the decompressor is restricted to P or not.

13

Summary: Four Quantities

Parts I and II introduce four quantities. Two are object-intrinsic invariants (γ and Hs ); two are algorithm-dependent measures (Tad and OCout ). Table 1 summarises them.

30

Table 1: The four quantities introduced in this paper. γ and Hs are object-intrinsic invariants; Tad and OCout are algorithm-dependent measures. All four are defined in terms of K and the running-time notation of hypothesis (H2). Symbol γ(x)

Definition min

d : |d|≤K(x)+c0

TU (d)

Object

What it measures

Input

Min. decompression time from a near-shortest description

Tad (A, x)

TA (x)/K(x)

Input

Work per bit of genuine input information

OCout (A, x)

TA (x) − |A(x)|

Output

Overhead beyond writing the output

Hs (y)

K(y)/ log2 |y|

Output

Information density the solution

of

Invariance. γ is invariant up to polynomial factors across universal machines (Theorem 4.2). Hs is invariant up to O(1/ log |y|) additive terms, since K changes by at most c0 across universal machines and log |y| is fixed. Tad and OCout depend additionally on the algorithm A. Independence. Low Hs does not imply γ = O(K) (Proposition 12.3(i)), and does not imply γP < ∞ unconditionally (Proposition 12.3(ii)). Whether low Hs implies polynomially bounded γ is open. Their joint behaviour characterises instance difficulty: • Structured instances (industrial SAT, structured TSP): when solutions are structurally guided in the sense of Definition 4.13 (low Hs of solutions, polynomial decompression time relative to instance size), Theorem D guarantees polynomial-time solvability unconditionally. • Random instances (random SAT near threshold, worst-case TSP): high Hs of solutions; under P ̸= NP, Theorem B establishes superpolynomial γP (in the strict sense of Definition 2.6) for the explicit family Fc0 . The practical/worst-case gap in NP problems is reflected in the contrast between the two regimes: structured instances satisfy the conditions of Definition 4.13, while random instances do not. Computability. γ and Hs are not computable (since both are defined via K, which is incomputable by the classical theorem of [11]; see also Remark B.1). Practical use requires computable proxies: LZ-based approximations for K, empirical running times for γ, and compressor output sizes for Hs .

31

Conclusion The gap identified in Section 1.1, between the existence of a short description and the computational cost of using it, has been formalised, characterised, and connected to the central open problem of complexity theory. What this paper contributes is not a new angle on P = NP but a new quantity: γP (x), the minimum cost of recovering x from a near-shortest description via a polynomial-time decompressor. This quantity has three properties that, to the authors’ knowledge, no prior measure combines: it is machine-independent (Theorem A); it is unconditionally non-trivial, in the sense that no polynomial bounds it everywhere (Theorem B’); and it admits an exact biconditional characterisation of P = NP among certificates with K(xw ) = Ω(|w|), in the standard Turing model (Theorem C, Remark 4.8). For certificates with K(xw ) ≪ |w|, γP = ∞ unconditionally — itself a manifestation of constrained inaccessibility. The four-quantity framework of Parts I and II — γ, Tad , OCout , Hs — provides a language for a distinction that standard complexity theory does not make: between instances that are hard in the worst case and instances that are tractable in practice because their solutions carry low information density and are efficiently decompressible. Theorem D establishes polynomial-time tractability unconditionally for any family satisfying the structural conditions of Definition 4.13. The open questions of Section 9 mark the natural boundary of what the framework currently establishes. The most immediate is Question Q5: a quantitative relation between γ and K t would clarify the position of γ within the spectrum K → K t → Kt → γ and is the missing piece for a complete picture of how the four classical measures and γ relate to one another.

Further Directions This paper will be extended to show that the results established here subsume those obtained independently in the author’s work published this month (see [1]). Their unification gives rise to a new class of phenomena, of which constrained inaccessibility is the foundational instance: the existence of a proof for a problem whose solution does not belong to the space of admissible solutions. To the authors’ knowledge, no analogous phenomenon has been identified in the existing literature. The relationship of P = NP to this class, and the precise sense in which this differs from classical undecidability and computational intractability, are examined in forthcoming work.

A

Classical Measures as Limiting Regimes; Grammar Gap Details

This appendix has two parts. The first part (Section A.1) derives the four classical measures (K, K t , Kt, H) as limiting regimes of γ (cited in Section 6). The second part contains the full proof of Lemma 8.2 (Grammar complexity gap), of which a proof sketch appears in Section 8.

32

A.1

Classical measures as limiting regimes of γ

The four classical information measures — Kolmogorov complexity K, time-bounded Kolmogorov complexity K t , Levin’s Kt, and Shannon entropy H — each arise as a limiting or relaxed regime of γ. K as the length-constrained foundation. γ(x) imposes two constraints: descriptions must be near-shortest (|d| ≤ K(x) + c0 ) and the minimisation is over running time. Removing the near-shortest constraint entirely — minimising TU (d) over all programs d with U (d) = x — does not simply recover K(x): the minimum running time over all descriptions lies in the range [K(x), |x| + O(1)], but need not equal K(x). (For x = 0n , the shortest program has length O(log n) but runs in Θ(n) steps, so the minimum running time is Ω(log n), not O(log n).) What the near-shortest constraint does do is force the minimisation to range over descriptions whose length is provably close to K(x), isolating the computational cost of compact encodings from the cost of verbose but fast ones. K t as the dual of γ. K t (x) = min{|d| : U (d) = x in ≤ t steps} fixes time and minimises length. γ(x) fixes near-minimal length and minimises time. They are dual in direction: every lower bound on K t constrains the set of short programs that halt within t steps, while every lower bound on γ constrains the set of fast programs that are near-shortest. The trade-off is captured by the open problem in Question Q5 (Section 9). Kt as a weighted single-objective relaxation. Levin’s Kt(x) = mind {|d|+log2 TU (d) : U (d) = x} trades off length and log-time in a single objective. γ(x) separates the two: it imposes a hard constraint on length (|d| ≤ K(x) + c0 ) and then minimises time exactly. When the description length and running time trade-off is smooth, minimising |d| + log2 TU (d) produces a solution near the Pareto frontier of (length, time). The nearshortest constraint in γ pins to the shortest end of this frontier. P Shannon entropy as the distributional limit. Shannon entropy H(X) = − x p(x) log2 p(x) is the expected description length under an optimal code for source X. For a uniformly random string X of length n, E[K(X)] = n + O(1) and H(X) = n, so the two agree up to O(1) in that case [11, Theorem 2.1.1]. For stationary ergodic sources, K(X1 · · · Xn )/n → H almost surely [11, Theorem 4.5.3], where H is the entropy rate. γ is the pointwise (per-string) counterpart that adds running time: it asks about the decompression cost of a specific object x, not the expected cost over a distribution. Shannon entropy has no analogous pointwise extension that captures computational cost.

A.2

Full proof of Lemma 8.2: grammar complexity gap

Proof. We verify the three claims of Lemma 8.2 in detail. Setup. Over the alphabet {a, b} (identified with {0, 1} via a 7→ 0, b 7→ 1), define 1

2

n

x = a b a b · · · a b,

n X = Θ(n2 ). N = |x| = (i + 1) = n(n+3) 2 i=1

33

Proof of (i): g ∗ (x) = Θ(n). Upper bound. The grammar G∗ defined in the proof sketch has 2n + 2 rules (1 for S, n − 1 for Bi with 1 ≤ i < n, 1 for Bn , n for Ai with 1 ≤ i ≤ n, 1 for A0 ). Thus |G∗ | = 2n + 2 = O(n). Lower bound. Since G∗ is an SLP, every non-terminal generates a fixed substring of x (determined by its unique production). The n blocks a1 , a2 , . . . , an are pairwise non-overlapping substrings of x with pairwise distinct lengths 1, 2, . . . , n. In any SLP generating {x}, two distinct blocks ai and aj (i ̸= j) cannot be generated by the same nonterminal: that non-terminal would expand to the same fixed string in every occurrence, but ai ̸= aj . Therefore the√SLP requires at least n distinct non-terminals (one per block length), so g ∗ (x) ≥ n = Ω( N ). Note on generality. This argument applies to SLPs. For general CFGs, the lower bound requires a separate argument (since non-terminals in a CFG may generate different strings depending on context); we omit this generalization as the paper works throughout with SLPs (Theorem 4.11). Proof of (ii): Tderive (G∗ ) = Ω(n). The derivation of the block ai via Ai requires the i chain Ai ⇒ aAi−1 ⇒ a2 Ai−2 ⇒ · · · ⇒ ai AP 0 ⇒ a , a chain of i + 1 steps. The total number + 1) + n = Θ(n2 ) = Θ(N ). In particular of derivation steps for the entire string is ni=1 (i√ the maximum chain depth is n + 1 = Ω(n) = Ω( N ). Proof of (iii): existence of G′ with |G′ | = O(n) and Tderive (G′ ) = O(log N ). G∗ is a straight-line program (SLP): every non-terminal has just one production, and the grammar is acyclic (productions only reference non-terminals of strictly smaller index). Applying Theorem 4.11 (Ganardi–Jeż–Lohrey [6]) to G∗ yields an equivalent SLP G′ with: (a) |G′ | = O(|G∗ |) = O(n), so |G′ | ≤ g ∗ (x) + cg for the constant cg of Definition 8.1 and sufficiently large n; and (b) Tderive (G′ ) = O(log N ) = O(log n). The transformation preserves L(G′ ) = L(G∗ ) = {x} by correctness of the GJL algorithm [6]. Therefore G′ is near-minimal and has logarithmic derivation depth.

B

Full Proof of Theorem B’: Unconditional Lower Bound on γ

We prove Theorem 4.10 in full. Theorem (B’ restated). For every polynomial p, there exists y ∈ {0, 1}∗ such that γ(y) > p(|y|). Consequently, γ is not polynomially bounded on {0, 1}∗ . Proof. Suppose for contradiction that γ(y) ≤ p(|y|) for all y and some fixed polynomial p. We derive an algorithm that computes K(y) to within an additive constant c0 , contradicting the classical incomputability of K [11]. The algorithm B. On input y of length n: (1) P Enumerate all self-delimiting programs d with |d| ≤ n + c0 . There are at most n+c0 k n+c0 +1 such programs; all can be listed explicitly in finite time. k=0 2 < 2 34

(2) For each d in the enumeration, simulate U (d) for at most p(n) steps. (3) Among all d that halt within p(n) steps and produce output y, record the minimum length m∗ = min{|d|}. (4) Output m∗ . Correctness. We claim m∗ = K(y) (to within c0 ). Upper bound m∗ ≤ K(y) + c0 : by definition of the enumeration, every d with |d| ≤ K(y) + c0 is included in step (1). Lower bound m∗ ≥ K(y): every program d counted in step (3) satisfies U (d) = y, so |d| ≥ K(y) by definition of K(y) as the infimum of lengths of programs producing y. It remains to show that step (3) finds at least one near-shortest description of y that halts within p(n) steps. By the hypothesis γ(y) ≤ p(n) and Definition 2.1, there exists a near-shortest description d′ of y (with |d′ | ≤ K(y) + c0 ) such that TU (d′ ) = γ(y) ≤ p(n). Since K(y) ≤ n + O(1) (Proposition 3.5) and c0 is chosen large enough to absorb this O(1) (hypothesis (H1)), we have |d′ | ≤ K(y) + c0 ≤ n + 2c0 . The program d′ is therefore included in the enumeration of step (1) (which covers all |d| ≤ n + c0 , and 2c0 is absorbed into the constant by choosing c0 large enough), halts within p(n) steps, and produces y. Therefore d′ is recorded in step (3), and m∗ ≤ |d′ | ≤ K(y) + c0 . Conclusion. Algorithm B computes a value m∗ satisfying K(y) ≤ m∗ ≤ K(y) + c0 for every y, in finite time (the simulation in step (2) runs for at most p(n) steps per program, and there are finitely many programs). This contradicts the classical theorem that K is not computable [11]: K is Turing-incomputable because computing it would solve the halting problem ([11], Chapter 3). Therefore the hypothesis γ(y) ≤ p(|y|) for all y is false, and there exists y with γ(y) > p(|y|). Remark B.1 (Relationship to computability). The proof shows that if γ were polynomially bounded everywhere, K would be computable — a contradiction. Therefore γ itself is not computable: no Turing machine computes γ(y) for all y. This is consistent with Theorem 4.2 (invariance up to polynomials), which does not require γ to be computable.

C

An Optimal Decompressor Incurs Only Constant Overhead Beyond Its Output

This appendix makes explicit a relationship between OCout (Definition 11.1) and the decompressor efficiency ratio ρ (Definition 11.4) that follows from combining those definitions with Proposition 3.5, but is not stated in Section 11. For an algorithm A operating in the decompressor regime with output y = A(x), the definitions give directly: TA (x) = OCout (A, x) + |y|, and therefore: ρ(A, x) =

TA (x) OCout (A, x) + |y| = . γ(y) γ(y)

Proposition C.1 (Overhead of an optimal decompressor). If A is an optimal decompressor in the sense of Definition 11.4 — that is, ρ(A, x) = 1 — then OCout (A, x) = O(1).

35

Proof. From ρ(A, x) = 1: TA (x) = γ(y). By Proposition 3.5, γ(y) ≤ |y| + O(1). Therefore: OCout (A, x) = TA (x) − |y| = γ(y) − |y| ≤ O(1). Since OCout (A, x) ≥ 0 by Proposition 11.2, we conclude OCout (A, x) = O(1). Remark C.2 (Interpretation). Proposition C.1 gives a precise operational meaning to optimality in the decompressor regime: a decompressor is optimal if and only if it performs no computation beyond writing its output, up to O(1) overhead. Every step beyond O(1) overhead is accounted for by the output itself. This is the tightest possible sense in which a decompressor can be said to be computationally efficient: it wastes no steps on internal computation beyond what is strictly required to produce the output.

Acknowledgments The author used an artificial intelligence based language assistant to support text revision, translation, and bibliography formatting. All scientific ideas and conclusions are the author’s own.

References [1] Fabio F. G. Buono. Syntactic systems cannot see semantic invariants. arXiv:2606.17275, 2026. arXiv preprint. [2] G. J. Chaitin. A theory of program size formally identical to information theory. Journal of the ACM, 22(3):329–340, 1975. [3] M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, and A. Shelat. The smallest grammar problem. IEEE Transactions on Information Theory, 51(7):2554–2576, 2005. [4] S. A. Cook. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), pages 151–158. ACM, 1971. [5] V. Estivill-Castro and D. Wood. A survey of adaptive sorting algorithms. ACM Computing Surveys, 24(4):441–476, 1992. [6] M. Ganardi, A. Jež, and M. Lohrey. Balancing straight-line programs. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1169–1183. IEEE, 2019. [7] H. H. Hoos and T. Stützle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2004. [8] A. N. Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1(1):1–7, 1965. 36

[9] N. J. Larsson and A. Moffat. Offline dictionary-based compression. Proceedings of the IEEE, 88(11):1722–1732, 2000. [10] L. A. Levin. Universal sequential search problems. Problems of Information Transmission, 9(3):265–266, 1973. [11] M. Li and P. M. B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, New York, 3 edition, 2008. [12] K. Mehlhorn. Sorting presorted files. In Proceedings of the 4th GI-Conference on Theoretical Computer Science, volume 67 of Lecture Notes in Computer Science, pages 199–212. Springer, 1979. [13] C. G. Nevill-Manning and I. H. Witten. Identifying hierarchical structure in sequences: A linear-time algorithm. Journal of Artificial Intelligence Research, 7:67–82, 1997. [14] C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27(3):379–423, 1948. [15] J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5):530–536, 1978.

37