{"id":"06492852-1eaf-4ccd-a83f-9a9a97f9ed02","arxiv_id":"2606.31370","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Introduces witness complexity γ(x) measuring expansion time of near-shortest descriptions, proving polynomial invariance, conditional separation from KC under P≠NP, and a biconditional characterization of P=NP via the relative variant γP.","lead":"This paper defines witness complexity γ(x) as the minimum running time to expand near-shortest descriptions of a string on a universal Turing machine. It positions the measure as relevant for evaluating short keys and certificates in time-bounded cryptographic protocols.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"gam definition requires identifying near-shortest descriptions (uncomputable) and fixed UTM; invariance claim may not fully insulate later results","rationale":"The reader’s weakest_assumption already isolates the definitional prerequisite that every subsequent claim rests on. Because the manuscript text was not supplied to the reader, no stronger internal inconsistency can be diagnosed; the definitional point remains the single most load-bearing modelling choice.","tokens_in":1731,"tokens_out":431,"duration_ms":24020,"concrete_test":"Extract the exact definition of “near-shortest” and the invariance statement (likely §2 or §3). Re-prove the invariance claim for two different thresholds (additive c=0 vs. multiplicative 2·KC(x)) on the same UTM; if the polynomial degree or the constant in the invariance changes by more than a fixed factor independent of x, the downstream class-relative results are not robust.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central object is gam(x) := min { runtime of program p | |p| ≈ KC(x) }. All stated results (invariance up to poly factors, conditional separation under P\neq NP, biconditional characterisation of P=NP via gP, tractability for structured NP families) are stated for this measure. The definition therefore presupposes (a) a fixed universal TM and (b) a precise quantifier for “near-shortest” (additive constant? multiplicative? length ≤ KC(x)+c). Because KC is uncomputable, the set over which the min is taken is not recursively enumerable in general; any proof that moves from the existential definition to a complexity-class statement must therefore justify that the choice of UTM and of the “near” threshold does not affect the class membership or the separation. The abstract asserts invariance up to polynomial factors, but does not indicate whether the invariance proof is uniform in the threshold parameter or only for a fixed additive constant. If the latter, the conditional separation and the gP characterisation become sensitive to that modelling choice.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1945,"tokens_out":564,"duration_ms":24635,"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":[{"comment":"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.","section":"Definition of gam(x)"},{"comment":"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.","section":"Invariance claim"},{"comment":"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.","section":"Characterization of P=NP via gP"}],"minor_comments":[{"comment":"The abstract refers to 'Part II' without indicating whether the current manuscript contains both parts or only Part I; clarify the scope.","section":"Abstract"},{"comment":"Notation: distinguish gam and gP from standard complexity notation to prevent reader confusion.","section":"Notation"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"[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."},{"response":"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_made":"yes","referee_comment":"[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."},{"response":"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_made":"yes","referee_comment":"[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."}],"tokens_in":1465,"tokens_out":729,"duration_ms":22263,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that this paper defines gam(x) as the min runtime over near-shortest programs for x on a fixed UTM, to highlight cases where low KC still means high expansion cost in crypto settings. It also introduces a class-relative gP and claims invariance up to poly factors, a conditional separation assuming P ≠ NP, an unconditional lower bound, a biconditional characterization of P = NP via gP, and tractability for some NP families.\n\nThe motivation from bounded-time protocols is straightforward and the distinction from plain KC is a reasonable angle for usability questions. The idea of tracking witness time separately from length is new in the cited literature.\n\nThe soft spots are central. gam(x) requires identifying the near-shortest descriptions first, but KC is uncomputable so that set is not recursively enumerable in general. The abstract states invariance up to polynomial factors without indicating whether the proof is uniform across thresholds or only for a fixed additive constant. If the latter, the conditional separation and the gP characterization of P = NP become dependent on modeling choices for the UTM and the exact meaning of “near.” No derivations or sketches appear, so it is not possible to check whether those issues are handled.\n\nThis is for readers already working on fine-grained complexity measures with crypto applications. Someone looking for new definitions might skim the measure and the P = NP link, but the work does not yet supply enough verifiable detail to engage seriously. I would not send it to peer review.","headline":"The new gam measure tries to capture expansion time for near-shortest descriptions but its definition runs into uncomputability that undercuts the invariance and separation claims.","tokens_in":2414,"tokens_out":380,"would_cite":false,"duration_ms":8921,"reading_group":"no","serious_thinker":"unclear","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Low Kolmogorov complexity can coexist with high witness complexity for short string descriptions.","keywords":["witness complexity","Kolmogorov complexity","P versus NP","cryptographic verification","short descriptions","universal Turing machine","NP tractability"],"falsifier":"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.","tokens_in":2623,"feed_emoji":"⏱️","tokens_out":641,"duration_ms":40132,"temperature":0.7,"pith_summary":"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.","feed_headline":"Low KC strings can have high witness complexity","feed_subtitle":"gam(x) measures runtime of near-shortest descriptions and can exceed polynomial bounds even when KC is low, with a conditional separation fr","key_machinery":"witness complexity gam(x), the minimum running time over near-shortest descriptions of a string on a universal Turing machine","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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"],"fun_headline_variants":["Low KC strings can need high witness complexity","gam(x) separates from Kolmogorov complexity","Low KC does not guarantee fast witness time","Short descriptions may require long expansion"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The definition of gam(x) presupposes a fixed universal Turing machine and the ability to identify near-shortest descriptions.","fun_headline_variants_meta":{"raw":{"variants":["Low KC strings can need high witness complexity","gam(x) separates from Kolmogorov complexity","Low KC does not guarantee fast witness time","Short descriptions may require long expansion"]},"model":"grok-4.3","cost_usd":0.003233,"raw_usage":{"total_tokens":1662,"prompt_tokens":684,"num_sources_used":0,"completion_tokens":50,"cost_in_usd_ticks":32328000,"prompt_tokens_details":{"text_tokens":684,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":928,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":684,"tokens_out":50,"duration_ms":8017,"temperature":1.0,"reasoning_tokens":928,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-01T05:34:41.678654+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}