{"id":"236cf61b-ec5f-453b-9cb4-a75e935fce1f","arxiv_id":"2606.04257","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A new conjecture called Kolmogorov Hardness claims complexity hardness comes from inaccessible random-string facts, and conditionally implies PH noncollapse, SAT notin P/poly, one-way functions, and more.","lead":"The paper proposes that many separate hardness conjectures in complexity theory share one cause: efficient methods should not get usable help from true facts about random strings that the proving theory cannot itself verify. It shows that if this principle is accepted, it would imply dozens of open conjectures, but the principle itself is unproved.","discovery_kind":"unclear","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The hierarchy-level payoff is ungrounded: Lemma 3.8 asserts without proof that a finite approximation of a true-Π_i oracle predicate lies in Π^p_{i+1}, so SETH-K-PH is not a well-defined PH statement and Theorem 3.10's derivation of PH noncollapse does not follow from KH.","rationale":"The reader's weakest-assumption analysis is sound: HRC/Feasible Reflection is the foundational unproven converse, and the Level-Respecting Certification Bridge is another no-cheating step. I agree those are the deepest axiomatic uncertainties. But for the paper's main advertised technical consequence, there is a more immediate, concrete problem. Even if HRC and KH were granted, the hierarchy-level machinery in §3.2 does not currently cohere. Definition 3.7 promises a 'finite bounded approximation' of an oracle for true Π_i sentences; Lemma 3.8 then asserts the resulting predicate lies at the next level of the polynomial hierarchy. The proof of Lemma 3.8 is only a uniformity sketch and never shows that the approximation agrees with the actual oracle-Kolmogorov predicate R^t_i. Since the main conditional result (Theorem 3.10) uses Lemma 3.8 to convert PH collapse into a P^{Π^p_i} decision procedure for Q^t_i, the gap is load-bearing. The paper itself concedes in §6 that no formal independence or counterexample analysis supports the core principles; my concern is narrower and more tractable: define one level-i predicate completely, or remove the claim that it 'expresses' oracle Kolmogorov randomness. Because the issue is a formalization gap rather than a demonstrated contradiction, a conditional verdict with a required repair is appropriate; if the repair is impossible, the hierarchy-level half of the paper should be withdrawn.","tokens_in":26298,"tokens_out":8356,"duration_ms":88198,"concrete_test":"Formalize Definition 3.7 for i=1: give the exact Π^p_1 predicate that answers a query of the form ∀y TM_e(y) halts during a t(n)-step simulation by U^(1), and prove that all such queries can be answered by a uniform Π^p_1 predicate. If answering this Π_1-complete class of queries is not in Π^p_1, Lemma 3.8 fails and SETH-K-PH is not a well-formed statement about PH. A complementary check: for small n, compute R^t_i membership under the true-Π_i oracle and under the proposed finite approximation; any divergence on inputs a PH machine can reach invalidates the bridge.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central technical payoff — PH noncollapse and SAT∉P/poly (Theorem 3.10, Corollary 3.11) — depends on Lemma 3.8, which claims that the finite predicate Q^t_{i,fin}(x) 'expressing x∈R^t_i' lies uniformly in Π^p_{i+1}. But R^t_i is defined using Kolmogorov complexity relative to an oracle for true Π_i sentences (the i-th Turing jump), while Definition 3.7 asks that every oracle query in the bounded computation be 'decidable by a predicate in Π^p_i' — the i-th level of the polynomial hierarchy. These are not the same objects: a query such as '∀y TM_e(y) halts' is Π_1-complete for the arithmetic hierarchy and is not decidable by any Π^p_1 predicate. The paper never specifies the 'finite bounded approximation' nor proves that it agrees with the true-Π_i oracle on the relevant t(|x|)-step computations. Consequently SETH-K-PH is an assumption about an ill-defined predicate; even granting HRC and KH as axioms, Lemma 3.8 does not establish the promised PH-level consequence. This is an internal formal gap, not a disagreement with prevailing conjectures.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a proof-theoretic meta-complexity assumption package centered on Kolmogorov Hardness (KH): a sound theory S should have polynomial-size proofs of bounded consistency of S+(x∈R) only when EA+Con_S already proves x∈R. From KH and its finite-scale and hierarchy-level strengthenings, the paper derives, conditionally, density-1 families of hard tautologies, no-mutual-help phenomena, PH noncollapse with explicit dense separators, SAT∉P/poly, and conditional routes to one-way functions, derandomization, natural-proofs compatibility, and Feige-style random-refutation hardness. The paper is explicit that HRC, KH, and the bridge principles are conjectural, and it discusses formal independence obstacles.","tokens_in":26711,"tokens_out":9059,"duration_ms":94793,"significance":"If the framework were sound, it would provide a genuinely unifying explanation of several major open problems, and the paper is commendably transparent about which steps are theorems and which are assumptions. The finite-scale consequences (Theorem 3.3, Corollaries 3.4–3.5) follow from SETH-K-Finite in a straightforward way, and Theorem 2.9 on machine invariance is a useful robustness check. However, the hierarchy-level payoff is built on an invalid identification of arithmetical truth oracles with polynomial-hierarchy predicates. Lemma 3.8 is not a minor gap: it is the load-bearing step for SETH-K-PH and therefore for Theorems 3.10 and 3.12. The paper remains a programmatic proposal, but its headline conditional consequences for PH noncollapse and SAT∉P/poly are not established as stated.","major_comments":[{"comment":"The finite predicate Q^t_{i,fin} is not a finite approximation of x∈R^t_i. R^t_i is defined relative to an oracle for the true Π_i sentences (the i-th Turing jump), while Definition 3.7 requires every oracle query to be decidable by a predicate in Π^p_i. For i=1, a single query can be a Π_1 sentence such as ∀s ¬Halt(e,0,s), which is Π_1-complete and is not decidable by any Π^p_1 = coNP predicate. Replacing the oracle by a PH-decidable predicate changes which strings are compressible in t steps, and the paper gives no argument that the two notions agree on the relevant bounded computations. Lemma 3.8 therefore does not place Q^t_{i,fin} in Π^p_{i+1}; it defines a different arithmetical predicate. Since Theorem 3.10 and Corollary 3.11 depend directly on Lemma 3.8, the PH noncollapse conclusion is unsupported even assuming SETH-K-PH.","section":"§3.2.1, Definition 3.7 and Lemma 3.8"},{"comment":"The theories T_i := S + Π^{true}_i are not recursively (or computably) axiomatizable for i≥1, since the set of true Π_i sentences is not c.e. for i≥1. The proof invokes 'relativized Chaitin-style incompleteness' to assert that T_i proves only finitely many true level-i randomness assertions. Chaitin's incompleteness theorem applies to effectively axiomatized sound theories; no formalization or proof is supplied for an oracle axiomatized theory. This is not a technicality: the contradiction in Theorem 3.15 depends exactly on this finiteness. Without a valid relativized Chaitin theorem for T_i, the derivation of SETH-K-PH from Certified Feasible Reflection and the Level-Respecting Certification Bridge is not established.","section":"§3.2.4, Theorem 3.15"},{"comment":"The Level-Respecting Certification Bridge asserts that if a polynomial-time Π^p_i-oracle machine correctly decides Q^t_i, then T_i certifies its accepting correctness on every sufficiently long true random input. This is not a bridge derived from any property of polynomial-time computation; it is a strong formal provability assumption, essentially as strong as the conclusion it is used to prove. Combined with the non-effectivity of T_i, the assumption is not backed by any supporting example, consistency check, or counterexample analysis. Consequently Theorem 3.15 is a derivation of SETH-K-PH from an assumption that already contains the key certificate existence claim, rather than an explanation of why a level-i decider must have such a certificate. This makes the hierarchy-level argument circular in a way that is not acknowledged in the text.","section":"§3.2.4, Assumption 3.14"}],"minor_comments":[{"comment":"The names SETH-K-Finite and SETH-K-PH are misleading: the assumptions have no evident relation to the Strong Exponential Time Hypothesis, and the acronym invites confusion.","section":"§3.2.2"},{"comment":"Theorem 4.2 states Liu–Pass as an equivalence for the value problem of time-bounded Kolmogorov complexity, but the paragraph immediately after warns that the decision/MINKT variant should be cited instead. This ambiguity matters because Theorem 4.6 relies on the formulation; the statement and the caveat should be reconciled.","section":"§4.2, Theorem 4.2 and surrounding text"},{"comment":"The notation 'R tt_t' appears malformed; it should likely be R^{tt}_t or a similar typographically distinct symbol. Please fix the notation to avoid confusion with R^t_i.","section":"§4.3"},{"comment":"The internal/external reading distinction is useful, but the claim that the ∀x closure of KH is Π^0_2 should be displayed explicitly with the formalized quantifier structure, since the exact complexity depends on the arithmetization of 'S has poly-size proofs' and of 'x∈R'.","section":"§6"}],"recommendation":"reject","confidential_remarks":"The paper is an ambitious programmatic proposal, and its transparency about conjectural status is a strength. However, the main technical payoff — PH noncollapse and SAT∉P/poly from SETH-K-PH — rests on an internal category error: arithmetical truth oracles are identified with PH predicates in Lemma 3.8, and the theories T_i in Theorem 3.15 are not effectively axiomatizable. These are not presentation issues; they invalidate the stated derivation. The finite-scale results and the framework's conceptual organization could be salvageable in a revised version, but the hierarchy-level claims would need a fundamentally different formulation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe thing to know: this is a genuinely ambitious unifying framework, but the main complexity-theoretic payoff does not currently go through. The stress-test note is right. Lemma 3.8 conflates the arithmetic hierarchy with the polynomial hierarchy. The randomness predicate R^t_i is defined relative to an oracle for true Π_i sentences—the i-th Turing jump. Queries to that oracle are not decidable by Π^p_i predicates; deciding whether a given Π_i sentence is true is an arithmetic-hierarchy problem, not a polynomial-hierarchy problem. So the \"finite bounded approximation\" in Definition 3.7 is not obviously a PH predicate, and SETH-K-PH is not a well-defined statement about a PH-complexity problem. Without a proof that the finite approximation agrees with the true-Π_i oracle on the relevant bounded computations, you cannot conclude Π^p_i ≠ Π^p_{i+1}. This is a formal gap, not just a philosophical worry.\n\nThat said, the paper earns real credit elsewhere. The cleanest parts are the unconditional positive direction—EA-level relative consistency implies simulation—and the Busy Beaver transfer from Monroe's earlier work. The HRC/KH distinction is a useful way to organize a family of conjectures, and the finite-scale density theorems and no-mutual-help observations are concrete and clearly presented. Section 6 is commendably honest about the absence of independence results and about the standardness obstacles. The paper is well structured and transparent about what is assumed.\n\nThe soft spots beyond Lemma 3.8 are real but proportionate. HRC is the load-bearing conjecture and is supported mainly by a no-cheating intuition; the Level-Respecting Certification Bridge and Boundary Calibration assumptions do a lot of work. The paper admits these are conjectural, so the weakness is acknowledged, but the hierarchy-level edifice still rests on the unproved Lemma 3.8.\n\nWho is this for? Someone working on meta-complexity or proof-complexity conjectures who wants a map of how Kolmogorov randomness might unify several hardness assumptions. But that reader should be warned: the PH-noncollapse and SAT∉P/poly implications are not established in this draft.\n\nMy recommendation: send it to a serious referee. The framework is interesting enough to deserve careful review, but it needs major revision—either replace the true-Π_i oracle with a genuinely PH-level notion, or prove the finite-approximation lemma. I would not cite the PH-noncollapse claim as it stands.","headline":"The framework is worth a referee, but the strong PH-noncollapse result currently rests on a formal gap: Lemma 3.8 conflates arithmetic truth with the polynomial hierarchy.","tokens_in":27132,"tokens_out":3264,"would_cite":false,"duration_ms":38416,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03F30","03F20","68Q15","68Q30"],"pacs":[],"model":"deepseek-v4-flash","headline":"True random facts are unusable by feasible proofs unless a weak base theory already explains them; from that single principle the paper derives conditionally PH noncollapse, SAT not in P/poly, and routes to cryptography and random-refutatio","keywords":["Kolmogorov randomness","bounded consistency","proof complexity","polynomial hierarchy","meta-complexity","one-way functions","derandomization","random 3-SAT refutation"],"falsifier":"Take a fixed sound theory S (say S^1_2 plus its own consistency), pick a true string x that is Kolmogorov-random in the logarithmic-deficiency sense and not provably so over EA+Con_S, and check whether S has proofs of Con_{S+(x∈R)}(n) of length n^c for infinitely many n. A single such proof family, found by any means other than an EA-level relative-consistency proof, would refute KH. More directly, construct a nonstandard model of S with a standard cut containing such polynomial-size proof codes while the weak-base implication fails.","tokens_in":26126,"feed_emoji":"🧩","tokens_out":8335,"duration_ms":82574,"temperature":0.7,"pith_summary":"This paper tries to establish that a single information constraint organizes the major hardness conjectures of complexity theory. The constraint, Kolmogorov Hardness (KH), says that a sound arithmetic theory cannot efficiently prove the consistency of adjoining a true Kolmogorov-random fact—x is random—unless that fact is already provable over a weak base theory (EA plus the theory's consistency). If KH holds, difficult conditional consequences follow: random strings generate dense families of exponentially hard tautologies, a hierarchy-level strengthening separates every adjacent level of the polynomial hierarchy and rules out SAT having polynomial-size circuits, and calibrated variants lead to one-way functions, derandomization, and random 3-SAT refutation hardness. The paper also argues that KH behaves like a reflection principle and may be formally independent of standard metatheories, and it lays out a research program for testing the principle.","feed_headline":"One randomness rule links P vs NP, PH, and one-way functions","feed_subtitle":"If feasible proofs need weak-base explanations for random facts, PH noncollapse, SAT not in P/poly, and more follow.","key_machinery":"Bounded-consistency simulation and the HRC/Feasible Reflection converse. For theories S⊇S^1_2, S simulates S+φ if S has polynomial-size proofs of Con_{S+φ}(n). The known positive direction is that EA⊢Con_S→Con_{S+φ} implies simulation. The key machinery is the proposed converse—simulation only if that weak-base implication holds—specialized to φ=(x∈R). KH then uses standard incompleteness arguments to supply infinitely many random axioms inaccessible over EA+Con_S. The finite-scale variant SETH-K-Finite and the hierarchy-level variant SETH-K-PH add the algorithmic and circuit-theoretic calibration needed to turn the proof-theoretic obstruction into concrete complexity separations.","core_discovery":"The paper's central claim is a proposed exact converse to a known proof-complexity mechanism. It is known that if a weak base theory EA proves Con_S→Con_{S+φ}, then S has polynomial-size proofs of Con_{S+φ}(n), i.e., S simulates S+φ. The paper's Higher Relative Consistency (HRC) / Feasible Reflection principle asserts the converse: no polynomial-size proof family for a true extension exists without such an EA-level explanation. Specializing to φ being a true statement 'x∈R' (x is Kolmogorov-random), this becomes Kolmogorov Hardness (KH): a sound theory cannot efficiently prove consistency of adjoining an inaccessible random fact. The paper then shows that finite-scale and hierarchy-level str","pith_inferences":["A concrete way to pressure-test the program is to prove or disprove the HRC converse in weak fragments of bounded arithmetic; a counterexample there would show exactly where the 'no-cheating' principle breaks.","If KH is independent of standard metatheories, its role would be closer to a reflection principle than a theorem; the paper's own program treats this as an open target.","The framework suggests that meta-complexity problems like time-bounded Kolmogorov complexity are hard because they sit on the boundary between weak-base-accessible randomness and inaccessible randomness; this boundary could be formalized and tested against known hardness results."],"forward_implications":["If KH holds, for every sound theory S and all but finitely many true random strings x, S lacks polynomial-size proofs of Con_{S+(x∈R)}(n); this yields a density-1 family of polynomial-size tautologies requiring exponential-size proofs.","If SETH-K-PH holds, the polynomial hierarchy is infinite: Π^p_i ≠ Π^p_{i+1} for every i≥1, with explicit dense separating predicates; the standard advice-collapse argument then gives SAT∉P/poly.","With the average-case boundary reflection and boundary calibration assumptions, KH transfers to one-way functions via the known equivalence with mild average-case hardness of time-bounded Kolmogorov complexity.","With sparse Feige hardness and refutation reflection, KH implies the random 3-SAT refutation hypothesis at constant clause density.","KH and HRC imply that no sufficiently strong sound theory simulates its own consistency extension, and a self-applicable KH principle implies the theory's own consistency, so it cannot be proved inside that theory."],"fun_headline_variants":["Randomness as proof barrier yields P vs NP, PH, and crypto","Kolmogorov Hardness: one axiom for P vs NP, PH, and OWFs","A single meta-assumption unifies P vs NP, PH, and one-way functions","One rule: hard randomness implies PH noncollapse and P≠NP"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that feasible simulation requires a weak-base relative-consistency explanation—the known sufficient condition (EA proving Con_S → Con_{S+φ}) is also necessary; at higher levels, an analogous level-respecting certification bridge must hold. If a polynomial-size proof family can exist without such an explanation, KH and all its consequences collapse.","fun_headline_variants_meta":{"raw":{"variants":["Randomness as proof barrier yields P vs NP, PH, and crypto","Kolmogorov Hardness: one axiom for P vs NP, PH, and OWFs","A single meta-assumption unifies P vs NP, PH, and one-way functions","One rule: hard randomness implies PH noncollapse and P≠NP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000945,"raw_usage":{"total_tokens":3944,"prompt_tokens":885,"completion_tokens":3059,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":629,"completion_tokens_details":{"reasoning_tokens":2972}},"tokens_in":629,"tokens_out":3059,"duration_ms":20810,"temperature":1.0,"reasoning_tokens":2972,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T12:25:12.079606+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a fixed sound theory S (say S^1_2 plus its own consistency), pick a true string x that is Kolmogorov-random in the logarithmic-deficiency sense and not provably so over EA+Con_S, and check whether S has proofs of Con_{S+(x∈R)}(n) of length n^c for infinitely many n. A single such proof family, found by any means other than an EA-level relative-consistency proof, would refute KH. More directly, construct a nonstandard model of S with a standard cut containing such polynomial-size proof codes while the weak-base implication fails.","supporting_citations":[],"review_version":2}