P ≠ NP Precisely Because P = NP: Sections of Propositional Truncation and Three Levels of the Gap

Status of this paper. This is a position paper. It contains no proof of P ≠ NP and does not claim to contain one. It contains a precise reformulation, one unconditional theorem, one proposition assembled from known results, a classification conjecture, a structural conjecture equivalent to P ≠ NP, and a ladder of fragments on which this conjecture can be attacked step by step. We reformulate the P versus NP question as a question about the existence of a uniform, polynomial-time section of propositional truncation, ‖A(φ)‖ ⊸ A(φ), for the family of 3-SAT witnesses, in a type system T that characterises the class P in the spirit of Soft Linear Logic (Lafont) and Light Linear Logic (Girard). We distinguish three levels at which a gap can appear between intension (the witness) and extension (the fact that a witness exists): logical, symmetric and resource. At the logical level there is no gap: for a finite, ordered domain the section exists in plain HoTT. At the symmetric level we prove unconditionally that no categorically natural section exists; we stress that this obstruction is purely symmetric, does not depend on resource bounds, and applies to 2-SAT as well. At the resource level we assemble known results into a proposition about the branching model L (self-reduction with unit propagation and a fixed order): the section L is polynomial for 2-SAT and Horn-SAT, but exponential for 3-SAT and, contrary to a naive reading of Schaefer's dichotomy, for XOR-SAT, under every fixed order. We propose that the boundary is drawn here not by polymorphisms but by propagation safety: we prove that it is sufficient and state its necessity as a conjecture. Ruling out a section in the whole of T is equivalent to P ≠ NP; we state it as a conjecture and propose a ladder of increasingly strong fragments as a programme for attacking it. We make the title formula precise through a parameter N, the number of witnesses. For N = 1 the logical and the symmetric gap vanish, while the Valiant–Vazirani theorem implies that the resource gap remains (unless NP = RP). Equality at two levels thus isolates the inequality at the third, and this is the exact content of the thesis “P ≠ NP precisely because P = NP”. Along the way we distinguish two inequalities: an informational one, the log₂ N bits erased by truncation, which vanishes at N = 1, and a computational one, which remains.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-16
DOI
https://doi.org/10.5281/zenodo.24266424
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

P ≠ NP Precisely Because P = NP: Sections of Propositional Truncation and Three Levels of the Gap

Jan Jagielski
2 links
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

P ≠ NP Precisely Because P = NP: Sections of Propositional Truncation and Three Levels of the Gap

Jan Jagielski
preprint en

Abstract

Status of this paper. This is a position paper. It contains no proof of P ≠ NP and does not claim to contain one. It contains a precise reformulation, one unconditional theorem, one proposition assembled from known results, a classification conjecture, a structural conjecture equivalent to P ≠ NP, and a ladder of fragments on which this conjecture can be attacked step by step. We reformulate the P versus NP question as a question about the existence of a uniform, polynomial-time section of propositional truncation, ‖A(φ)‖ ⊸ A(φ), for the family of 3-SAT witnesses, in a type system T that characterises the class P in the spirit of Soft Linear Logic (Lafont) and Light Linear Logic (Girard). We distinguish three levels at which a gap can appear between intension (the witness) and extension (the fact that a witness exists): logical, symmetric and resource. At the logical level there is no gap: for a finite, ordered domain the section exists in plain HoTT. At the symmetric level we prove unconditionally that no categorically natural section exists; we stress that this obstruction is purely symmetric, does not depend on resource bounds, and applies to 2-SAT as well. At the resource level we assemble known results into a proposition about the branching model L (self-reduction with unit propagation and a fixed order): the section L is polynomial for 2-SAT and Horn-SAT, but exponential for 3-SAT and, contrary to a naive reading of Schaefer's dichotomy, for XOR-SAT, under every fixed order. We propose that the boundary is drawn here not by polymorphisms but by propagation safety: we prove that it is sufficient and state its necessity as a conjecture. Ruling out a section in the whole of T is equivalent to P ≠ NP; we state it as a conjecture and propose a ladder of increasingly strong fragments as a programme for attacking it. We make the title formula precise through a parameter N, the number of witnesses. For N = 1 the logical and the symmetric gap vanish, while the Valiant–Vazirani theorem implies that the resource gap remains (unless NP = RP). Equality at two levels thus isolates the inequality at the third, and this is the exact content of the thesis “P ≠ NP precisely because P = NP”. Along the way we distinguish two inequalities: an informational one, the log₂ N bits erased by truncation, which vanishes at N = 1, and a computational one, which remains.

Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon