pith. sign in

arxiv: 2606.31370 · v1 · pith:NIH4VQMOnew · submitted 2026-06-30 · 💻 cs.CR · cs.CC

Witness Complexity of Short Descriptions: A Cryptographic Perspective

Fabio F.G. Buono This is my paper

Pith reviewed 2026-07-01 05:34 UTC · model grok-4.3

classification 💻 cs.CR cs.CC
keywords witness complexityKolmogorov complexityP versus NPcryptographic verificationshort descriptionsuniversal Turing machineNP tractability
0
0 comments X

The pith

Low Kolmogorov complexity can coexist with high witness complexity for short string descriptions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces witness complexity gam(x) as the minimum running time needed to execute near-shortest descriptions of a string x. It shows that this measure can be large even when the Kolmogorov complexity KC(x) is small, which is relevant for cryptographic settings that require bounded-time verification of short keys or certificates. The results include polynomial invariance of gam, a conditional separation from KC assuming P not equal to NP, an unconditional lower bound, a biconditional characterization of P equal to NP using the relative class gP, and tractability results for structured NP families. Part II extends this with companion measures showing gaps in grammar-based complexity.

Core claim

Witness complexity gam(x) is defined as the minimum running time over near-shortest descriptions of x on a universal Turing machine. The paper proves that low KC can coexist with high gam, with invariance up to polynomial factors, a conditional separation assuming P ≠ NP, an unconditional lower bound from the incomputability of KC, a biconditional characterization of P = NP via gP, and polynomial-time tractability for structured NP families. This positions gam as a metric for the usability of keys and certificates in time-bounded protocols.

What carries the argument

witness complexity gam(x), the minimum running time over near-shortest descriptions of a string on a universal Turing machine

If this is right

  • gam(x) is invariant up to polynomial factors across universal machines
  • There is a conditional separation between KC and gam assuming P ≠ NP
  • An unconditional lower bound on gam follows from the incomputability of KC
  • P equals NP if and only if the class-relative variant gP satisfies the corresponding property
  • Structured families in NP admit polynomial-time computation of gam

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Protocol designers may need to measure both description length and expansion time when selecting cryptographic keys or certificates.
  • The unconditional gap between grammar size and derivation cost indicates similar runtime distinctions could apply to other syntactic measures.

Load-bearing premise

The definition of gam(x) presupposes a fixed universal Turing machine and the ability to identify near-shortest descriptions.

What would settle it

An algorithm that always finds, for any x with low KC(x), a near-shortest description running in time polynomial in the description length would falsify the claim that low KC can coexist with high gam.

read the original abstract

In cryptographic practice, where protocols impose strict time bounds, implementations demand predictable resource usage, and real-world systems require immediate verification for security and usability, a short key or certificate is useful only if it can be expanded or verified within a bounded time; otherwise 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 \emph{witness complexity} \(\gam(x)\), the minimum running time over near-shortest descriptions of a string on a universal Turing machine. \(\gam\) differs from Shannon entropy and Kolmogorov complexity \(\KC\): low \(\KC\) can coexist with high \(\gam\). We prove invariance up to polynomial factors; a conditional separation (assuming \(\PneqNP\)). An unconditional lower bound from incomputability of \(\KC\); a biconditional characterisation of \(\PeqNP\) via the class-relative variant \(\gP\); and polynomial-time tractability for structured \(\classNP\) families. Part II develops companion measures and shows an unconditional gap between grammar size and derivation cost, positioning \(\gam\) as a metric for the usability of keys and certificates.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper introduces witness complexity gam(x) as the min running time over near-shortest descriptions of x on a UTM. It claims low KC can coexist with high gam, proves invariance up to polynomial factors, a conditional separation assuming P≠NP, an unconditional lower bound from KC incomputability, a biconditional characterization of P=NP via the class-relative gP, and polynomial-time tractability for structured NP families. Part II develops companion measures showing an unconditional gap between grammar size and derivation cost.

Significance. If the claims hold, gam provides a time-bounded usability metric for short cryptographic objects (keys, certificates) that standard KC does not capture, with potential implications for protocol design. The P=NP characterization via gP and tractability results for structured families would be notable contributions to complexity theory if the underlying definitions are shown to be robust.

major comments (3)
  1. [Definition of gam(x)] Definition of gam(x) (abstract and §2): gam(x) is defined via minimization over near-shortest programs, but KC is uncomputable so the domain is not r.e. The paper must explicitly fix the 'near' threshold (additive constant c, multiplicative factor, etc.) and prove that all later results (invariance, conditional separation, gP characterization) are invariant under this choice and under change of UTM.
  2. [Invariance claim] Invariance claim (abstract): the statement that gam is invariant 'up to polynomial factors' must be shown to be uniform in the nearness parameter; if the proof fixes an additive constant, the conditional P≠NP separation and the biconditional via gP become sensitive to that modeling choice and may not transfer to other reasonable thresholds.
  3. [Characterization of P=NP via gP] Characterization of P=NP via gP (abstract): because membership in gP relies on the same uncomputable minimization, the paper must supply a rigorous argument that the class is well-defined and that the biconditional is not an artifact of the chosen UTM or nearness threshold.
minor comments (2)
  1. [Abstract] The abstract refers to 'Part II' without indicating whether the current manuscript contains both parts or only Part I; clarify the scope.
  2. [Notation] Notation: distinguish gam and gP from standard complexity notation to prevent reader confusion.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and valuable comments on the definition and robustness of witness complexity. We address each major comment below and will revise the manuscript accordingly to strengthen the formal foundations.

read point-by-point responses

  1. Referee: [Definition of gam(x)] Definition of gam(x) (abstract and §2): gam(x) is defined via minimization over near-shortest programs, but KC is uncomputable so the domain is not r.e. The paper must explicitly fix the 'near' threshold (additive constant c, multiplicative factor, etc.) and prove that all later results (invariance, conditional separation, gP characterization) are invariant under this choice and under change of UTM.

    Authors: We agree that an explicit fixed threshold is required for rigor. In the revision we will define gam(x) using a concrete additive constant c=1 (programs of length at most KC(x)+1) and prove that all stated results—polynomial invariance, the P≠NP separation, and the gP characterization—hold for any fixed additive constant c, with the polynomial degree allowed to depend on c. The proofs already rely on standard UTM simulation overheads that are absorbed into the polynomial factors; we will make the uniformity explicit in a new subsection of §3. revision: yes

  2. Referee: [Invariance claim] Invariance claim (abstract): the statement that gam is invariant 'up to polynomial factors' must be shown to be uniform in the nearness parameter; if the proof fixes an additive constant, the conditional P≠NP separation and the biconditional via gP become sensitive to that modeling choice and may not transfer to other reasonable thresholds.

    Authors: The invariance argument in §3 is already parameterized by the nearness constant. We will add an explicit lemma showing that if two UTMs and two additive constants c and c' are used, the resulting gam functions differ by at most a polynomial factor whose degree depends only on c and c'. Consequently the conditional separation (which relies on the existence of strings with low KC but high gam) and the gP biconditional remain valid for any fixed choice; the modeling choice affects only the concrete polynomial, not the qualitative claims. This will be stated clearly in the revised §3 and abstract. revision: yes

  3. Referee: [Characterization of P=NP via gP] Characterization of P=NP via gP (abstract): because membership in gP relies on the same uncomputable minimization, the paper must supply a rigorous argument that the class is well-defined and that the biconditional is not an artifact of the chosen UTM or nearness threshold.

    Authors: We will supply the requested argument. The class gP is defined relative to a fixed UTM and fixed additive constant; we will prove that the statement 'P=NP if and only if gP=P' is independent of these choices by showing that any two such definitions differ by a polynomial-time reduction that preserves the equality to P. Well-definedness follows because gP is the set of languages L for which there exists a polynomial p such that membership in L is decidable in time p(n) given an oracle for the witness-complexity predicate at the chosen threshold; the biconditional then transfers directly. The new subsection will contain the full reduction argument. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results derived from independent definition

full rationale

The paper defines gam(x) as the min runtime over near-shortest descriptions and states theorems (invariance up to poly factors, conditional separation under P≠NP, unconditional lower bound from KC incomputability, biconditional via gP, tractability for structured NP families) as consequences. No quoted equations or self-citations reduce any claimed result to the definition by construction, nor do any predictions collapse to fitted inputs. The measure is introduced independently of the properties proved about it, satisfying the self-contained criterion.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract, no explicit free parameters, ad-hoc axioms, or invented entities beyond the new definition of the measure itself are detailed.

pith-pipeline@v0.9.1-grok · 5727 in / 968 out tokens · 37986 ms · 2026-07-01T05:34:41.678654+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    Fabio F. G. Buono. Syntactic systems cannot see semantic invariants. arXiv:2606.17275, 2026. arXiv preprint

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  2. [2]

    G. J. Chaitin. A theory of program size formally identical to information theory. Journal of the ACM, 22(3):329–340, 1975

    1975

  3. [3]

    Charikar, E

    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

    2005

  4. [4]

    S. A. Cook. The complexity of theorem-proving procedures. InProceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), pages 151–158. ACM, 1971

    1971

  5. [5]

    Estivill-Castro and D

    V. Estivill-Castro and D. Wood. A survey of adaptive sorting algorithms.ACM Computing Surveys, 24(4):441–476, 1992

    1992

  6. [6]

    Ganardi, A

    M. Ganardi, A. Jež, and M. Lohrey. Balancing straight-line programs. InProceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1169–1183. IEEE, 2019

    2019

  7. [7]

    H. H. Hoos and T. Stützle.Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2004

    2004

  8. [8]

    A. N. Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1(1):1–7, 1965. 36

    1965

  9. [9]

    N. J. Larsson and A. Moffat. Offline dictionary-based compression.Proceedings of the IEEE, 88(11):1722–1732, 2000

    2000

  10. [10]

    L. A. Levin. Universal sequential search problems.Problems of Information Trans- mission, 9(3):265–266, 1973

    1973

  11. [11]

    Li and P

    M. Li and P. M. B. Vitányi.An Introduction to Kolmogorov Complexity and Its Applications. Springer, New York, 3 edition, 2008

    2008

  12. [12]

    Mehlhorn

    K. Mehlhorn. Sorting presorted files. InProceedings of the 4th GI-Conference on Theoretical Computer Science, volume 67 ofLecture Notes in Computer Science, pages 199–212. Springer, 1979

    1979

  13. [13]

    C. G. Nevill-Manning and I. H. Witten. Identifying hierarchical structure in se- quences: Alinear-timealgorithm.Journal of Artificial Intelligence Research, 7:67–82, 1997

    1997

  14. [14]

    C. E. Shannon. A mathematical theory of communication.Bell System Technical Journal, 27(3):379–423, 1948

    1948

  15. [15]

    Ziv and A

    J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5):530–536, 1978. 37

    1978