An Entropic Perspective on P vs NP: Reformulation via Kolmogorov Complexity

We present a unified framework for the known equivalence between the P vs NP problem and resource-bounded Kolmogorov complexity, framing it as an entropic reformulation. The paper does not prove P != NP; instead it gives a cautious information-theoretic presentation of the witness-entropy gap, distinguishes known equivalences from new terminology, and identifies the remaining uniformity bridge as the central open challenge. CHANGELOG Changes in Version 1.6 (June 2026) Critical: The entropy-threshold discussion now explicitly avoids the overstrong circuit-sequence reading: the moderate EH-style threshold yields only an s log s = Omega(n)-type circuit-size lower-bound target under direct circuit descriptions, not an NP not subset P/poly or NP not subset SIZE(2^o(n)) conclusion. Major: MCSP and related compression-bridge claims are kept conditional on an additional circuit-to-SAT incompressibility bridge, rather than being presented as immediate consequences of the entropy reformulation. Major: The Advice-Front leakage ledger and the planted/easy/OGP control matrix are integrated as diagnostic guardrails: same-run references, instance-dependent advice and planted witnesses are treated as allowances or controls, not as external uniformity evidence. Minor: The combined bilingual PDF is now rebuilt through the reproducible build_kombi_pdf.py merge path with explicit metadata and link-audit checks. DE/EN: English, German and combined bilingual PDFs were rebuilt after the post-v1.5 proof/paper and design checks; the German text layer was checked for real umlauts and no visible mojibake markers. Changes in Version 1.5 (May 2026) Critical: The Capillary-Front section now separates the Shannon proxy H_front from the resource-bounded Kt/MDL front residue after BPF, template, advice, and specialization allowances. Critical: UB-PvNP is no longer stated as directly implying OWF existence or global SAT slice-entropy lower bounds; it is restricted to separation plus an explicit witness-entropy obstruction. Major: The EH/Slice-Entropy bridge is reframed as a stronger sufficient truth-table/circuit bridge target, not as an equivalence claim. Major: The German SAT-slice numerics are explicitly illustrative: Shannon H_slice is not identified with Kt(SAT_n). DE/EN: English, German, and combined bilingual PDFs were rebuilt after the 2026-05-17 proof/paper math hotfix; visible German umlaut and sharp-s residues were checked. Changes in Version 1.4 (May 2026) Critical: The compression bridge was weakened from a direct instance-compression route to an explicit open witness-to-compression transfer lemma. Major: OGP and slow-mixing language was restricted to restricted-class, front-shadow, and flow-shadow diagnostics; it is no longer stated as a general theorem against arbitrary polynomial-time algorithms. Major: Capillary-Front Filtration was added as a cautious diagnostic for low-complexity search fronts that reach positive witness mass. Major: Advice-currency and Bounded-Proof-Family guardrails were strengthened, including explicit preregistration language and separation of Shannon proxy, Kt/MDL residue, and front-cover counts. Minor: The Dirichlet-Atlas warning was integrated: same-run self-consistency is not an external uniformity bridge. DE/EN: English, German, and combined bilingual PDFs were rebuilt from the 2026-05-16 strict-review candidate. Changes in Version 1.3 (May 2026) Critical: Claim strength reduced: the manuscript is now framed as a presentation and framework paper for known P-vs-NP/Kolmogorov-complexity equivalences, not as an independent separation result. Major: Priority and related-work notes for Orponen--Ko--Schöning--Watanabe, Fortnow, Allender, Hirahara, Liu--Pass, and Santhanam were strengthened throughout the EN/DE text. Major: Advice-Erosion and Search-Flow Conductance were added as heuristic bridge diagnostics; the Bounded-Proof-Family guardrail clarifies that entropy, OGP, advice, or conductance signals only count when carried by a pre-specified bounded proof/solver/witness family. Major: MCSP and proof-complexity bridge routes were sharpened while marking their hypotheses and quantitative losses explicitly. Minor: Hodge/Kolyvagin analogies and numerical evidence language were softened; Post-Zookeeper transfer language was restricted to operational normal-form guidance. DE/EN: English, German, and combined bilingual PDFs were rebuilt from the 2026-05-06 local candidate. Changes in Version 1.2 (March 2026) Major: Instance compression bridge strategy elaborated (Remark rem:compression-bridge): 3-step argument via Fortnow–Santhanam no-sparsification connecting witness-finding to PH collapse Minor: Remaining quantifier-order gap explicitly identified Changes in Version 1.1 (March 2026) Major: Resolution-Width Conjecture connecting proof complexity to entropic hardness Major: Resolution width as thermodynamic observable Minor: Bibkeys unified, AC0 entropy obstruction proposition