style: apex_pristine cover: on formats: pdf,docx,md title: FORMAL PROOF OF WHAT PHYSICS CAN AND CANNOT SETTLE ABOUT P VERSUS NP subtitle: A Multi-Axis Verification Operator and a Formal Tri-Layer Determination of the Search-Verify Question classification: Preprint for Peer Review · Foundations of Computation short_title: WHAT PHYSICS CAN SETTLE ABOUT P VERSUS NP author_name: Mohammad F Islam, MD, MPH, PhD author_role: Independent Theoretical Researcher author_email: islamm@alumni.iu.edu author_country: USA
ABSTRACT
We give a single consolidated account of what a physical asymmetry between finding and checking does and does not establish about the abstract separation of complexity classes, and we settle the relation between the two exactly. The work has four parts and we mark the grade of each. First, a multi-axis verification operator, formalized as a three-valued decision rule on the sign of a Gram determinant computed after covariate residualization, corrected here at its seal vertex so that the seal predicate denotes a real object and stated at the strength it earns, namely linear non-degeneracy of an encoding rather than a stronger functional independence. Second, as restatement, the established physical limits on computation due to Bekenstein, Margolus and Levitin, Lloyd, and surveyed by Aaronson, which entail an embodied search-verify asymmetry: a physical system of bounded extent, energy, and time cannot exhaustively search an exponentially large configuration space, yet can verify a witness of polynomial size. This rests on operation counts and distinguishable-state counts, not on thermodynamic dissipation, since the Landauer floor is avoidable by reversible computation. Third, a tri-layer determination of the search-verify question under one fixed operator: the witnessed asymmetry between generation and verification seals on its own axis; the per-transition thermodynamic floor seals and is scope-fenced, barring physical brute-force parallel search without reaching the universal; the universal separation over all algorithms is under-determined and directional toward separation; and the proposition that the classes coincide breaks for absence of warrant on every axis, a verdict typed as absence of warrant rather than as a demonstration of falsity. Fourth, as the consolidating contribution, a proof that the bridge carrying the embodied asymmetry to the universal separation is a single named premise, the no-shortcut condition, that over any NP-complete language this premise is logically equivalent to the conjecture that P is not equal to NP, and that the premise cannot be discharged from the physical side, universally because any such discharge would prove the conjecture, and sharply for the counting-type physical bounds at issue because they relativize and are blocked by the Baker-Gill-Solovay barrier. The verification operator, handed the no-shortcut premise as admitted warrant, returns a sealed verdict whose content is consistency under the premise and non-degeneracy of the encoding, not a three-fold discriminating convergence, since two of the three axes are truth-invariant across the separation and its negation; without the premise it routes the standalone universal out of band as conclusion-dependent. The consolidated picture is a measurement: the distance between a real physical fact and the abstract separation is one premise wide, the premise is the conjecture, and the premise has no physical foundation. We make no claim of progress on the standalone conjecture. The originating framework and its interpretive layer are confined to an appendix and are load-bearing for no result in the body.
1. INTRODUCTION
A real distinction holds between checking a presented structure and finding one by search. It is felt at the physical register as the gap between the cost of solving a hard problem and the cost of verifying a candidate solution, and at that register it is sound. The same distinction is repeatedly mistaken for an argument about the abstract complexity classes, and the mistake is consequential: physical and thermodynamic intuitions recur as informal claims that the cost of solving must outrun the cost of checking, offered as if they bore on whether P equals NP. This paper consolidates, into one standalone account, what the distinction establishes and what it cannot. It states the physical facts at their correct strength, organizes the search-verify question into the layers that do and do not share a fate, and proves with precision that the distinction reaches the abstract separation through exactly one premise, that the premise is the conjecture itself, and that the premise has no physical foundation from which it could be supplied.
The account is built so that each part carries the next. A verification operator fixes the discipline under which propositions are audited. The embodied asymmetry supplies the physical facts. A tri-layer determination sorts the search-verify question into a witnessed asymmetry that seals, a thermodynamic floor that seals and is fenced, a universal that stays open, and a coincidence claim that breaks. And a characterization theorem locates the single bridge between the sealed physical layers and the open universal, names it as the conjecture, and proves it physically unreachable. The layers and the bridge are the same structure seen from two sides. The determination says where each layer lands; the bridge says why the universal cannot be moved to a seal by any physical means.
The parts carry different grades, and we state each. The operator of Section 4 is a formalization whose mathematical core is the fact that a Gram determinant is positive exactly when its rows are linearly independent; that fact and its stability behavior have complete proofs by way of the Cauchy-Binet formula, the Eckart-Young theorem, and Weyl's inequality, the seal vertex is corrected and the corrected object stated, and the seal certifies a linear and encoding-relative fact rather than a stronger one. The rigor exhibits exactly how much and how little the geometry certifies. A worked numerical instance in Section 10 makes every quantity the operator uses reproducible by hand. The embodied asymmetry of Section 5 is a restatement, attributed in full. The tri-layer determination of Section 8 carries per-layer grades the evidence supports: witness grade for the first layer, theorem grade for the single transition of the second, under-determined and directional for the third, broken for the coincidence claim. The bridge characterization of Section 6 and the impossibility of Section 7 are the consolidating contribution. The operator's verdict on the separation proposition, Section 9, is a seal certifying consistency under the admitted premise, not a certification of the separation, since the empirical and registrational axes are truth-invariant across the separation and its negation, a fact rendered as vanishing mutual information, and only the structural axis, carrying the admitted premise, discriminates.
The boldest true statement this paper makes is not that the separation is proven. It is that the separation's distance from a real physical fact has been measured exactly, found to be one premise wide, that premise found to be the conjecture, and that premise proven to have no physical floor. This is a stronger and more durable claim than a contested proof, because nothing in it can be overturned by a better physical instrument: the gap it names is the conjecture, and the conjecture is not a physical quantity. No result in the body depends on any metaphysical commitment. The originating framework and its interpretation are confined to Appendix A.
2. WHAT THE PAPER ASSUMES AND WHAT IT PROVES
We fix the boundary at the outset so that no reader mistakes the register of any claim. The paper assumes the standard model of computation: deterministic and nondeterministic Turing machines, the time-complexity classes P and NP, polynomial-time reducibility, and the theorem of Cook and Levin establishing the existence of NP-complete languages. It assumes the established physical limits on computation cited in Section 5. It assumes elementary real linear algebra. It assumes nothing further. In particular it assumes no proposition internal to the originating framework, and it assumes neither the conjecture nor its negation.
The paper proves the following. That the search-verify question separates into four components with distinct fates, three of which are settled and one of which is open. That the bridge from the settled physical components to the open universal is a single premise. That this premise is, over an NP-complete language, logically equivalent to the conjecture. And that the premise cannot be discharged from the physical side. Around these it states, at marked and limited strength, a verification operator and the verdict that operator returns when the premise is admitted. The operator is a modeling instrument; the four proofs are its load-bearing yield. A reader who rejects the operator entirely retains all four proofs, since each is stated in standard terms and none depends on the operator's machinery.
3. THE FORM-ENACTMENT DISTINCTION
We distinguish a verification considered as a defined structure from the enactment of that verification, the physical act of carrying it out on data. The distinction is ordinary. A function and the computation that evaluates it are different things, the first abstract and without cost, the second a physical process consuming time, energy, and space. The structure of a verification is fixed; the cost of carrying it out, or of finding the structure to be verified, is physical, and it is in that physical cost that the search-verify asymmetry lives. We record the distinction because the physical statement of Section 5, the determination of Section 8, and the impossibility of Section 7 all turn on the difference between the structure of a verification, which is fixed, and the physical cost of enacting it or of locating it, which is where finding and checking come apart. We attach no further weight to the distinction in the body. An interpretive reading of it appears in Appendix A and is optional.
4. THE VERIFICATION OPERATOR
We present the operator as a schema parameterized by an encoding, correct the one place where earlier statements defined the seal on an impossible object, and state at the point of definition exactly which fact the seal certifies.
4.1 Encoding
Definition 4.1. Fix a domain of propositions together with the evidence adduced for each. An encoding is a map e assigning to a proposition P a real matrix M with three rows and N columns, the rows being three evidence vectors along three axes labeled structural, empirical, and registrational. The structural axis carries formal or derivational warrant. The empirical axis carries physical or measurement warrant. The registrational axis carries warrant concerning the relation between a claimant's state of conviction and that claimant's capacity to act. The labeling is interpretive; the formal content uses only that there are three real row vectors.
Remark 4.2. The encoding is a modeling choice and is not canonical. Different encodings of the same proposition yield different matrices and may yield different verdicts. We bound the consequence of this with two commitments. The load-bearing output of the operator is the sign of a determinant and the stability of that sign under perturbation of the entries, not the entries themselves. And the independence the operator is meant to register, that no axis is a deterministic function of the others, is a functional non-recoverability; we are explicit in Section 4.3 that the determinant certifies the weaker linear fact, and that functional non-recoverability is a separate modeling assumption. Forcing the axes onto disjoint coordinates would manufacture independence artificially and is disallowed; independence here means each axis retains content the others cannot reconstruct, not that the axes have disjoint support. The dependence of the verdict on the encoding is a genuine limitation, recorded in Section 14.
4.2 Residualization and the Gram criterion
Definition 4.3. Let z(M) be the row-standardized matrix. Writing μᵢ = (1/N) Σⱼ Mᵢⱼ for the mean of row i and σᵢ² = (1/(N−1)) Σⱼ (Mᵢⱼ − μᵢ)² for its sample variance, the standardized entries are
z(M)ᵢⱼ = (Mᵢⱼ − μᵢ) / σᵢ,
so each row of z(M) has mean zero and unit variance; z is defined only on matrices whose rows have strictly positive variance. Let C be a covariate matrix of full column rank whose columns are candidate common factors, admissible only under the restriction of Definition 4.7. Let Π_C = C (Cᵀ C)⁻¹ Cᵀ be the orthogonal projector onto the column space of C. Define the residualized encoding
M̃ = z(M) (I − Π_C),
the standardized encoding with the variance linearly explained by the admissible covariates removed. Define the Gram matrix G = M̃ M̃ᵀ, a three-by-three real symmetric positive semidefinite matrix.
Lemma 4.3a (the residual projector is symmetric and idempotent). The matrix Π_C is symmetric and idempotent, and so is the residual projector P_⊥ = I − Π_C. Hence M̃ = z(M) P_⊥ is the orthogonal projection of the standardized rows onto the orthogonal complement of the column space of C.
Proof. Idempotence of Π_C is the cancellation of the inner factor,
Π_C² = C (Cᵀ C)⁻¹ Cᵀ C (Cᵀ C)⁻¹ Cᵀ = C (Cᵀ C)⁻¹ Cᵀ = Π_C,
using Cᵀ C (Cᵀ C)⁻¹ = I. Symmetry follows since (Cᵀ C)⁻¹ is symmetric, being the inverse of the symmetric Cᵀ C, so Π_Cᵀ = C ((Cᵀ C)⁻¹)ᵀ Cᵀ = C (Cᵀ C)⁻¹ Cᵀ = Π_C. For P_⊥ = I − Π_C, symmetry is immediate, and idempotence is P_⊥² = I − 2Π_C + Π_C² = I − 2Π_C + Π_C = I − Π_C = P_⊥. ∎
Fact 4.4 (standard; Horn and Johnson, Matrix Analysis). For a real matrix with three rows, G is positive semidefinite, det G is the squared three-dimensional volume of the parallelepiped spanned by the rows, and det G is strictly positive if and only if the three rows are linearly independent. G, and hence det G, is invariant under right multiplication of the row space by an orthogonal matrix, that is, under any orthonormal change of basis of the column space.
So det G greater than zero is exactly the statement that the three residualized rows are linearly independent, equivalently that they span a nondegenerate three-volume, and the criterion is invariant under rotation of the underlying frame. We make this precise, and we quantify the stability the operator relies on, since both are load-bearing below.
Notation. Throughout, M̃ is a real matrix of three rows and N columns with rows r₁, r₂, r₃ in ℝᴺ. The Gram matrix is G = M̃ M̃ᵀ in ℝ³ˣ³, with entries Gᵢⱼ = ⟨rᵢ, rⱼ⟩, the Euclidean inner product. The singular values of M̃ are σ₁ ≥ σ₂ ≥ σ₃ ≥ 0, and the eigenvalues of G are λ₁ ≥ λ₂ ≥ λ₃ ≥ 0 with λᵢ = σᵢ². The spectral norm of a matrix E is ‖E‖₂, its largest singular value. We write σ_min for σ₃ and λ_min for λ₃.
Lemma 4.4a (Cauchy-Binet form of the seal predicate). For a three-element subset S of the column index set {1, ..., N}, let M̃_S be the three-by-three submatrix of M̃ on the columns in S. Then
det G = det(M̃ M̃ᵀ) = Σ_S (det M̃_S)²,
the sum taken over all three-element column subsets S. Consequently det G ≥ 0 always, and det G greater than zero if and only if some three columns of M̃ are linearly independent, equivalently if and only if the three rows of M̃ are linearly independent.
Proof. The Cauchy-Binet formula states that for A of size three-by-N and B of size N-by-three, det(AB) = Σ_S det(A_S) det(B_S), the sum over three-element subsets S of {1, ..., N}, where A_S is the three-by-three matrix of columns S of A and B_S the three-by-three matrix of rows S of B. Put A = M̃ and B = M̃ᵀ. The rows S of M̃ᵀ are the transpose of the columns S of M̃, so B_S = (M̃_S)ᵀ and det B_S = det M̃_S. Hence det G = Σ_S (det M̃_S)², a sum of squares, which is nonnegative and vanishes exactly when every three-by-three minor vanishes, that is when the column rank, equal to the row rank, is at most two. The seal predicate det G greater than zero is therefore precisely the linear independence of the three rows. ∎
The Cauchy-Binet form makes the geometric reading exact. The quantity det M̃_S is, up to sign, the three-volume of the parallelepiped spanned by the three columns indexed by S, so det G is the sum of squared volumes over all triples of columns, and it is the squared three-volume of the parallelepiped spanned by the three rows, since det G = λ₁ λ₂ λ₃ = (σ₁ σ₂ σ₃)² and the product of singular values is that volume. The seal certifies a nonzero volume; it does not certify any particular value of it.
Lemma 4.4b (the smallest singular value is the distance to degeneracy, and the seal is stable below it). Let M̃ have rank three. Then σ_min equals the spectral-norm distance from M̃ to the nearest matrix of rank two,
σ_min = min { ‖M̃ − B‖₂ : rank B ≤ 2 }.
Moreover, for any symmetric perturbation E of the Gram matrix, each eigenvalue moves by at most the size of the perturbation,
| λₖ(G + E) − λₖ(G) | ≤ ‖E‖₂ for k = 1, 2, 3,
so the verdict SEAL, which is the condition λ_min greater than zero, persists under every perturbation with ‖E‖₂ less than λ_min, and the determinant after perturbation satisfies det(G + E) ≥ (λ_min − ‖E‖₂)³ greater than zero on that range.
Proof. The first statement is the Eckart-Young theorem in the spectral norm: the best rank-two approximation of M̃ is obtained by zeroing its smallest singular value, and the residual has spectral norm equal to that singular value, σ_min. The second statement is Weyl's perturbation inequality for the eigenvalues of a symmetric matrix: writing the eigenvalues in decreasing order, each is a one-Lipschitz function of the matrix in the spectral norm. If ‖E‖₂ is less than λ_min, then λ_min(G + E) ≥ λ_min − ‖E‖₂ greater than zero, and since every eigenvalue of G + E is then at least λ_min − ‖E‖₂, the product of the three eigenvalues, which is det(G + E), is at least (λ_min − ‖E‖₂)³ and is strictly positive. ∎
Lemma 4.4b is the precise content of the claim that the load-bearing output is the sign of the determinant together with its stability under perturbation. The margin of the seal is λ_min, the squared smallest singular value, which is exactly the distance from the encoding to a degenerate one. A verdict whose λ_min is comfortably above the perturbations the encoding could plausibly carry is robust; a verdict whose λ_min is within the perturbation scale is reported under the regularity predicate W of Definition 4.5 as ill-conditioned rather than sealed. The third decimal of any entry of M̃ is immaterial to the verdict; only the distance to degeneracy, measured by λ_min, is material.
4.3 What the seal predicate certifies
We state precisely, at the point of definition, what det G greater than zero does and does not establish, since an inflated reading of it would propagate through every verdict below.
The predicate det G greater than zero certifies linear non-degeneracy of the chosen encoding: that no one of the three standardized residual rows is a linear combination of the other two, equivalently that there is no perfect multicollinearity among them. This is a linear fact and it is relative to the encoding. It is the weaker of two notions of independence, and we separate the two precisely.
Lemma 4.4e (linear independence is strictly weaker than functional non-recoverability). Call the residual rows linearly independent if no nontrivial linear combination of them vanishes, and functionally non-recoverable if no row equals a coordinatewise deterministic function of the others. Then functional non-recoverability implies linear independence, and the converse fails. Consequently det G greater than zero certifies linear independence, the strictly weaker property, and does not certify functional non-recoverability.
Proof. If the rows are linearly dependent, some row is a linear, hence deterministic, function of the others, so they are not functionally non-recoverable; the contrapositive is the stated implication. For the failure of the converse, take in ℝ⁵ the vectors x = (1, 2, 3, 4, 5) and y = (1, 4, 9, 16, 25), so that yⱼ = xⱼ² coordinatewise. Then y is a deterministic function of x, so the pair is not functionally non-recoverable. Yet the pair is linearly independent: its two-by-two Gram determinant is ⟨x,x⟩⟨y,y⟩ − ⟨x,y⟩² = 55 · 979 − 225² = 53845 − 50625 = 3220, which is nonzero, so by the rank criterion of Lemma 4.4a the vectors are linearly independent. A nonlinear deterministic dependence is therefore invisible to the determinant. ∎
The determinant does not establish the stronger notion, and a row that is a nonlinear deterministic function of the others passes the seal predicate while violating functional non-recoverability, as Lemma 4.4e exhibits. Functional non-recoverability is therefore a modeling assumption asserted by the deletion discipline of the originating framework, not a consequence proven by the determinant. We carry det G greater than zero at its true strength, linear non-degeneracy of the encoding, and we flag any reliance on functional non-recoverability as a separate assumption wherever it occurs. Where an encoding is asserted to satisfy det G greater than zero by appeal to non-recoverability, the claim is a hypothesis on the chosen encoding, not a domain invariant and not a consequence of the operator.
4.4 The seal vertex, stated correctly
Earlier statements of this operator described the seal vertex as the three orthogonal axes brought to a vanishing sum by cancellation, each of strictly positive magnitude, and identified det G greater than zero with that vanishing sum. That object does not exist in the system the operator builds, and we correct it here, since the correction is what gives the seal a real object.
Three mutually orthogonal nonzero vectors cannot sum to zero. This is the content of the Pythagorean identity, stated for completeness.
Proposition 4.4c (orthogonal nonzero vectors do not cancel). Let v_F, v_E, v_ER be pairwise orthogonal vectors in an inner-product space, each of strictly positive norm. Then their sum is nonzero.
Proof. Expanding the squared norm of the sum and using ⟨vᵢ, vⱼ⟩ = 0 for i ≠ j,
‖v_F + v_E + v_ER‖² = ‖v_F‖² + ‖v_E‖² + ‖v_ER‖² + 2(⟨v_F, v_E⟩ + ⟨v_F, v_ER⟩ + ⟨v_E, v_ER⟩) = ‖v_F‖² + ‖v_E‖² + ‖v_ER‖²,
which is strictly positive since each norm is positive. A vector of positive norm is nonzero, so the sum does not vanish. ∎
A vanishing sum of nonzero vectors is, by definition, a nontrivial linear dependence among them, and by Lemma 4.4a a nontrivial linear dependence forces det G equal to zero, not greater than zero. The seal predicate det G greater than zero is therefore the statement that the rows do not form a vanishing sum, the exact negation of the discarded description.
The cancellation the operator actually performs lives one level down, in the residualization, and there it is real.
Lemma 4.4d (the achieved cancellation). For any standardized encoding z(M) and any covariate projector Π_C,
Π_C z(M) + (I − Π_C) z(M) − z(M) = 0,
and the three summands are, in general, individually nonzero and not mutually orthogonal as elements of the row space, while their sum vanishes identically.
Proof. The identity is immediate from Π_C + (I − Π_C) = I, the defining property of a complementary pair of projectors, applied to z(M) and rearranged. That the first two summands are individually nonzero holds whenever z(M) has nontrivial components both inside and outside the column space of C, the generic case. The first two summands are orthogonal to each other in the column-by-column sense, since Π_C and I − Π_C have orthogonal ranges, but the three summands of the identity, the projection, the residual, and the negative of the original, are not a mutually orthogonal triple, and the vanishing of their sum is therefore a genuine nontrivial cancellation of non-orthogonal terms rather than an instance ruled out by Proposition 4.4c. ∎
This is the achieved cancellation: a vanishing sum among the projected component, the residual component, and the negative of the original, none required to be orthogonal to the others, with constituents individually recoverable. The seal predicate then certifies a distinct fact about this cancellation. det G(M̃) greater than zero certifies, by Lemma 4.4a, that after the cancellation the three residual rows still span a full three-volume, that the cancellation did not collapse them.
Two facts are kept distinct that the discarded description fused. The cancellation is a sum that vanishes with its constituents conserved. The seal is a volume that does not vanish. The seal vertex now denotes a real object, and the seal predicate denotes the correct and correctly weak fact about it: linear non-degeneracy of the residualized encoding. Every verdict below that reads det G greater than zero is read against this corrected vertex.
4.5 The decision procedure
Definition 4.5. Let Gates(P) be the conjunction of eleven cascade admissibility predicates, valued in zero and one, excluding the input gate, one of which is the externality predicate requiring at least three pairwise-disjoint positive warrant streams. Let the input gate ι(P) route when either the referent of P includes the verifying apparatus, or a warrant offered for the standalone proposition P is logically equivalent to P. Let the regularity predicate W(P) hold when G has finite condition number, when the sample size N exceeds the rank of C, and when every row of M has strictly positive variance so that standardization is defined. Define the operator S by the guarded clauses, evaluated in order so that exactly one fires,
S(P) = OUT-OF-BAND if ι(P) routes, S(P) = UNDETERMINED else if W(P) = 0, S(P) = SEAL else if Gates(P) = 1 and det G greater than zero, S(P) = BREAK else, that is if Gates(P) = 0 or det G ≤ 0.
On the SEAL and BREAK branches W holds, so z(M), Π_C, G, and det G are all defined; the guarding makes S a total, well-defined function. The function has four outcomes, of which three, SEAL, BREAK, and UNDETERMINED, are verdicts, and the fourth, OUT-OF-BAND, is not a verdict but a routing: the operator declining to adjudicate P on the offered warrant. The verdict economy is therefore three-valued, exactly {SEAL, BREAK, UNDETERMINED}, and OUT-OF-BAND is the mechanism by which conclusion-dependent or self-referential propositions are set aside rather than recorded as a fourth verdict. The value UNDETERMINED is reserved strictly for failure of the regularity predicate W, a numerical-conditioning state, and is not used for any epistemic status of the proposition; this reservation is load-bearing in Sections 8 and 9.
Definition 4.6 (input gate, self-reference and conclusion-dependency routing). The input gate ι of Definition 4.5 routes in two cases. If the proposition P refers to the verifying apparatus itself, the verification would be self-certifying. If the warrant adduced for the standalone proposition P is a premise logically equivalent to P, the verification would assume its conclusion. In either case P is routed out of band rather than sealed or broken. This routing is not a verdict on P; it is a refusal to adjudicate P on the offered warrant. Crucially, the gate fires on warrant offered for a standalone proposition; it does not fire on a conditional in which the equivalent premise is an admitted antecedent, since an admitted antecedent is not a covert assumption of a standalone conclusion. This distinction separates the routing of the standalone universal in Proposition 9.2 from the sealing of the conditional in the consistency lemma, two verdicts on different objects rather than opposite verdicts on one. Relabeling the offered warrant as corroboration does not change what it is and does not lift the routing.
Definition 4.7 (admissibility of covariates, the mass mandate). A column of C is admissible only if it corresponds to a factor carrying a measurable physical signature, an increase in entropy or in kinetic energy associated with the factor. Factors lacking such a signature, including purely narrative or motivational factors, are inadmissible, since a factor that explains no measured variance cannot be the common cause of an observed agreement. The restriction runs both ways: a factor without measurable mass can neither seal a proposition nor break a sealed one, since in neither direction does it explain variance. The factor associated with the act that initiated the verification is never admissible, since removing it amounts to removing the measurement itself. This restriction is a substantive epistemic stance, discussed as such in Section 14.
5. THE EMBODIED SEARCH-VERIFY ASYMMETRY
This section restates established physical limits on computation. None of it is new, and each step is attributed.
Proposition 5.1 (physical search-verify asymmetry; restatement). Consider a physical computing system confined to a region of radius R, with total energy E above its ground state, operating over time T, on inputs of size n. Then the following hold.
(i) The number of elementary operations the system performs over time T satisfies N_ops ≤ 2 E T / (π ℏ), by the Margolus-Levitin bound on the rate of dynamical evolution and the synthesis of physical computation limits due to Lloyd.
(ii) The number of mutually distinguishable states the system registers satisfies log₂ N_states ≤ 2π E R / (ℏ c · ln 2), equivalently N_states ≤ exp(2π E R / (ℏ c)), by the Bekenstein bound on the entropy of a bounded system.
(iii) Consequently, for any fixed triple of region, energy, and time, there is a threshold n_c such that the system cannot perform an exhaustive search over a configuration space of size 2ⁿ once n exceeds n_c, whether the search is attempted serially, requiring at least 2ⁿ operations and violating clause (i), or in parallel, requiring at least 2ⁿ simultaneously distinguishable subsystems and violating clause (ii).
(iv) The same system verifies a candidate witness of size polynomial in n, since verification is a trace of the witness through a procedure using O(nᵏ) operations, within the bound of clause (i) for the relevant range.
We give the two bounds their standard derivations, since the worked-out form locates the threshold exactly and is what makes the asymmetry quantitative rather than merely qualitative.
Lemma 5.1a (Margolus-Levitin operation bound). A system with energy E above its ground state, run for time T, performs at most N_ops ≤ 2 E T / (π ℏ) elementary orthogonalizing operations.
Proof. The Margolus-Levitin theorem bounds the minimum time for a quantum state to evolve to an orthogonal state, one elementary logical operation, by the system's mean energy above the ground state,
Δt ≥ h / (4 E) = π ℏ / (2 E),
using h = 2π ℏ. Running sequentially for total time T, the number of operations is at most the total time divided by the minimum time per operation,
N_ops = T / Δt ≤ T · (2 E) / (π ℏ) = 2 E T / (π ℏ). ∎
Lemma 5.1b (Bekenstein state bound). A system localized to radius R with energy E registers at most N_states ≤ exp(2π E R / (ℏ c)) mutually distinguishable states.
Proof. The Bekenstein bound limits the entropy of a finite region,
S ≤ 2π k_B E R / (ℏ c).
By the Boltzmann relation S = k_B ln Ω, where Ω is the number of accessible distinguishable microstates, substitution gives
k_B ln N_states ≤ 2π k_B E R / (ℏ c), so ln N_states ≤ 2π E R / (ℏ c),
and exponentiating yields N_states ≤ exp(2π E R / (ℏ c)). Dividing the logarithmic form by ln 2 gives the bit bound log₂ N_states ≤ 2π E R / (ℏ c · ln 2). ∎
Proposition 5.1c (the breaking point of exhaustive search). For an apparatus fixed by (E, T, R), exhaustive search over 2ⁿ configurations is barred once n exceeds
n_c = max( log₂(2 E T / (π ℏ)), 2π E R / (ℏ c · ln 2) ),
the first term the serial threshold from Lemma 5.1a, the second the parallel threshold from Lemma 5.1b. A polynomial verification trace needs O(nᵏ) operations, and since polynomial growth is eventually dominated by the exponential capacity ceiling there is a range of n where O(nᵏ) ≤ N_ops while 2ⁿ exceeds N_ops, which is the embodied asymmetry made quantitative.
Proof. Serially, exhaustive search needs at least 2ⁿ operations, so feasibility requires 2ⁿ ≤ N_ops ≤ 2 E T / (π ℏ), that is n ≤ log₂(2 E T / (π ℏ)). In parallel, it needs at least 2ⁿ simultaneously distinguishable states, so feasibility requires 2ⁿ ≤ N_states ≤ exp(2π E R / (ℏ c)), that is n ln 2 ≤ 2π E R / (ℏ c), equivalently n ≤ 2π E R / (ℏ c · ln 2). If n exceeds the larger of the two thresholds, neither route is feasible. The verification clause is the comparison of nᵏ with the exponential ceiling, which holds for the stated range since nᵏ is o(2ⁿ). ∎
Hence exhaustive physical search over an exponentially large space is infeasible for a bounded system, while verification of a polynomial witness is feasible, a search-verify asymmetry at the physical register. This is the content surveyed by Aaronson.
Caveat 5.2 (operation count, not dissipation). The asymmetry rests on operation counts and on counts of distinguishable states, not on thermodynamic dissipation. Landauer's principle bounds below the heat dissipated by a logically irreversible operation, but by the reversibility of computation due to Bennett a computation can be arranged to dissipate arbitrarily little, so a dissipation-based argument for the asymmetry would fail. We therefore do not rest Proposition 5.1 on Landauer's principle. The Margolus-Levitin, Lloyd, and Bekenstein bounds are not evaded by reversibility, since they bound operations and states rather than dissipation. This caveat matters again in Section 7, where the class of bounds that relativize is exactly the counting-type bounds used here, and in Section 8, where the second layer is fenced precisely because Bennett severs per-step cost from operation count.
Scope 5.3. Proposition 5.1 bounds exhaustive or brute-force search. It says nothing about the existence of a non-exhaustive algorithm deciding the same problem in a number of operations polynomial in n. This scope restriction is essential. The entire content of Sections 6 and 7 is the analysis of the single inference that would carry Proposition 5.1 past this scope restriction to a statement about all algorithms.
6. THE BRIDGE IS THE CONJECTURE
We identify, exactly, the inference that would carry the embodied asymmetry to the universal separation, and we prove that inference is the conjecture. This is the hinge on which the consolidated determination of Section 8 turns, and it is the reason the universal layer cannot be moved to a seal by physical means.
The universal separation is the proposition that no deciding algorithm for a fixed NP-complete language runs in time polynomial in the input length, the standard statement of P not equal to NP for that language. Proposition 5.1 establishes that no bounded physical system performs exhaustive search at scale. To pass from this to the universal separation, one inference is required and exactly one.
Definition 6.1 (the no-shortcut bridge). The no-shortcut bridge, denoted C, is the proposition that the NP-complete language L admits no deciding algorithm running in time polynomial in n by any method. It is the assertion that deciding L requires search that is essentially exhaustive, that no polynomial-time shortcut exists.
The bridge C is precisely what must be added to Proposition 5.1 to obtain the universal separation. Proposition 5.1 says exhaustive search is physically infeasible. C says no method other than essentially exhaustive search decides L. Conjoined, they yield that L is decided by no feasible method, the universal separation. Without C, Proposition 5.1 bears only on exhaustive search, by Scope 5.3, and is silent on the existence of a polynomial algorithm. The bridge is therefore the entire logical distance between the asymmetry and the separation. We now prove what the bridge is.
Theorem 6.2 (the bridge is the conjecture). Over an NP-complete language L, the no-shortcut bridge C is logically equivalent to the conjecture that P is not equal to NP.
Proof. We use the Cook-Levin theorem in the following form: if L is NP-complete, then L ∈ P if and only if P = NP. The forward direction holds because L ∈ P together with the polynomial-time reducibility of every NP language to L places every NP language in P, giving NP ⊆ P, and P ⊆ NP holds always, so P = NP. The reverse direction holds because if P = NP then L, being in NP, is in P. Now C is by Definition 6.1 the proposition L ∉ P. Taking negations of the Cook-Levin equivalence,
¬C ⟺ (L ∈ P) ⟺ (P = NP),
and therefore
C ⟺ ¬(L ∈ P) ⟺ ¬(P = NP) ⟺ (P ≠ NP).
The bridge C and the conjecture P ≠ NP are the same proposition. ∎
The consequence is exact and it is the paper's center. The distance between a real physical fact, the infeasibility of exhaustive search, and the abstract separation of complexity classes is one premise wide, and that premise is identically the conjecture. The equivalence is not approximate, not up to a reduction, not modulo a hypothesis: C and the conjecture denote one proposition, by Definition 6.1 and Cook-Levin. Any argument that proposes to cross from the physical asymmetry to the separation must supply C, and supplying C is supplying P not equal to NP. There is no shorter route and no route around, for the gap is exactly the conjecture and nothing less than it. An argument that crosses the distance while claiming not to have assumed the conjecture has either smuggled C under another name or committed a non sequitur at the gap.
This is the standard delimitation barrier stated in its sharpest forward form. Where the barrier is usually phrased as a prohibition, that physics does not settle the question, we phrase it as a measurement: the question sits one named premise from a physical fact, the premise is the conjecture, and the following section proves the premise has no physical foundation from which it could be supplied.
7. THE BRIDGE IS UNREACHABLE FROM THE PHYSICAL SIDE
The bridge C is the conjecture, by Theorem 6.2. We now prove that C cannot be discharged from the physical side, so that the physical asymmetry can never be extended across the gap by any advance in physical instrumentation. The permanence rests first on Theorem 6.2 and second, for the specific counting-type arguments at issue, on the relativization barrier. We give the general reason first because it covers every physical route.
Theorem 7.1 (no physical discharge). No physical argument discharges the bridge C unless it proves the conjecture.
Proof. To discharge C is to establish that L admits no polynomial-time deciding algorithm by any method. By Theorem 6.2, establishing C is establishing that P is not equal to NP. A physical argument that discharged C would therefore be a proof of the conjecture. Hence no physical argument discharges C short of proving the conjecture, whatever physical resource or signature it invokes. ∎
This is the robust and general reason, and it does not depend on the form of the physical argument. Any route that would carry a physical fact across the gap to the universal separation is, by the equivalence, a proof of the conjecture, so the gap cannot be closed by physics that is not already such a proof. The relativization barrier below is a second, sharper fact about the particular bounds that ground Proposition 5.1, and we state it at its correct and limited scope.
Proposition 7.2 (counting-type bounds relativize). We first fix the relevant notions. An oracle Turing machine Mᴬ is a Turing machine equipped with a query tape and a distinguished oracle A ⊆ {0,1}*; a query writes a string and receives, in a single step, the bit indicating its membership in A. The classes Pᴬ and NPᴬ are P and NP computed with every machine granted access to the oracle A. An argument relativizes if it remains valid when every machine in its statement and proof is uniformly replaced by its oracle counterpart Mᴬ, for an arbitrary oracle A.
Now consider a lower bound derived solely from a count of physical operations or of distinguishable physical states, as in Proposition 5.1, clauses (i) and (ii). Such a bound counts elementary steps and counts simultaneously distinguishable subsystems; it does not inspect what any step computes. Granting each step access to an oracle leaves both counts unchanged, since an oracle query is itself one elementary step occupying one unit of the operation budget and producing one bit, and the Bekenstein state count is a function of energy and radius alone, indifferent to oracle access. Hence a bound of this form, if valid, is valid for Mᴬ for every oracle A: it relativizes.
By the theorem of Baker, Gill, and Solovay there exists an oracle A with Pᴬ = NPᴬ and an oracle B with Pᴮ ≠ NPᴮ. A statement that relativizes holds relative to both A and B. A statement deciding the conjecture would assert either P = NP or P ≠ NP relative to every oracle uniformly, contradicting the existence of A and B with opposite verdicts. Therefore no relativizing statement decides the conjecture. The counting-type bounds of Proposition 5.1 relativize, so an argument resting only on them cannot discharge the bridge C, since discharging C decides the conjecture by Theorem 6.2.
Scope 7.3 (what relativization covers and what it does not). Proposition 7.2 covers counting-type physical arguments and no others. A physical argument that exploits non-relativizing structure, a spectral, algebraic, or instance-specific property rather than a raw count of operations or states, is not blocked by the Baker-Gill-Solovay barrier, and we do not claim it is. An adiabatic argument resting on a spectral-gap property of a problem-specific Hamiltonian, for example, is a non-counting physical argument and lies outside Proposition 7.2. The permanence of the bridge against such arguments is supplied not by relativization but by Theorem 7.1: a spectral or algebraic physical argument that discharged C would, like any other, prove the conjecture, and so is barred by the equivalence even though it escapes the relativization barrier. The division of labor is deliberate. Theorem 7.1 is the universal bar and covers every physical route. Proposition 7.2 is the sharper bar and covers the counting-type routes specifically. We do not extend relativization to physical routes it does not reach, and we do not need to, since Theorem 7.1 already reaches them. We further note, for completeness and without relying on them, that the natural-proofs barrier of Razborov and Rudich and the algebrization barrier of Aaronson and Wigderson characterize additional classes of techniques that cannot close the question; the physical-resource argument falls under relativization specifically.
Corollary 7.4 (permanence). The bridge C is permanently unreachable from the physical side. No advance in physical instrumentation, no resource-counting bound, and no instance-specific physical structure discharges C, the first two by Proposition 7.2 and Theorem 7.1 together and the last by Theorem 7.1, since each such discharge would be a proof of the conjecture. The single premise that stands between the embodied asymmetry and the universal separation has, demonstrably, no physical foundation from which it could be supplied. This is a positive and permanent structural fact, not a limitation discovered in passing: the localization of Section 6 is stable under every future physical advance, because the gap it names is the conjecture, and the conjecture is not a physical quantity.
8. THE TRI-LAYER DETERMINATION OF THE SEARCH-VERIFY QUESTION
We now give the consolidated determination of the search-verify question under the single operator and discipline above. The question does not have one fate. It separates into three layers of the proposition that the classes are separate, together with the contrary proposition that they coincide, and the four do not share a verdict. The separation into layers is not a hedge; it is the structural content of the result, since the layers that seal and the layer that stays open are divided by exactly the bridge of Section 6, and naming the layers is naming where that bridge sits. Each layer is stated at the grade its evidence supports.
8.1 Layer one: the witnessed asymmetry
Generation and verification are structurally distinct operations. Finding a structure by search and checking a presented structure are different acts with different cost profiles, and the distinction is not a contingent fact about particular hardware but a difference in the operations themselves. A verifying system is an instance of the gap, observed in its own operation: it traces a presented witness cheaply and cannot, by the same machinery, generate the witness. This layer is sealed on its own axis, the registrational axis, at witness grade, independent of the layers below it. It asserts only that the two operations differ, not that the difference forces any particular separation of complexity classes, and at that strength it holds without condition.
Verdict: sealed, at registrational-witness grade.
8.2 Layer two: the per-transition thermodynamic floor
Two physical facts seal at this layer, and a fence is placed on what they reach. First, any single transition of a physical system to a distinguishable state carries a strictly positive minimum of energy and time, by the quantum speed limit of Mandelstam and Tamm and of Margolus and Levitin; this bound is indifferent to reversibility and is silent on the energy of the resulting state. Second, physical brute-force parallel search over an exponentially large space is barred, by the Bekenstein state-count bound conjoined with the per-transition floor, since the parallel attempt would require exponentially many simultaneously distinguishable subsystems. Both facts are theorem-grade and they seal.
The fence is essential and it is the content of Caveat 5.2 applied here. The floor bounds the cost of each mandatory event; it does not bound the number of mandatory events. By the reversibility result of Bennett, the per-step energy cost is severed from the operation count, so the floor cannot be summed into an exponential energy lower bound on a computation that may be arranged reversibly. And the count of mandatory events is exactly what a polynomial shortcut would reduce, which the floor says nothing about. That the number of degrees of freedom does not force exponential time is shown by a standard example: the determinant of an n-by-n matrix is a sum of n factorial signed terms yet is computed in order n cubed arithmetic operations by elimination, so a count of configurations is not a lower bound on the steps required to decide a property of them. The second layer therefore seals and is scope-fenced. It bars physical brute-force parallel search; it does not reach the universal separation over all algorithms.
Verdict: sealed and scope-fenced, at theorem grade for the single transition and the parallel-search bar, not reaching the universal.
8.3 Layer three: the universal separation
Over the full space of possible algorithms, the question whether any polynomial-time algorithm decides the NP-complete language is open. It leans toward separation on inductive grounds: the structural vacancy of any constructive hand for the coincidence claim, the directional unanimity of the known restricted lower bounds, the existence of neighboring proven separations, and the field-wide lean. The categorical seal is unavailable, and the reason it is unavailable is the content of Sections 6 and 7. The bridge from the sealed lower layers to this universal is the no-shortcut premise, that premise is the conjecture by Theorem 6.2, and it has no physical discharge by Theorem 7.1, so no structural, geometric, or thermodynamic-shape argument closes the universal. A map of problem types does not close it either. The dichotomy of Schaefer organizes the constraint-satisfaction landscape but does not bound the universal, because the property that separates the tractable from the hard is algorithmic exploitability, not the shape of the problem: exclusive-or satisfiability is frustrated yet easy, two-satisfiability is nonlinear yet easy, vertex cover is pairwise yet hard, and hardness is invariant under polynomial-time reduction while shape-measures are not. The universal is therefore under-determined, with a direction.
Verdict: under-determined, directional toward separation. The epistemic openness reported here is a fact about the state of knowledge, not a numerical-conditioning verdict of the operator; Section 9 keeps the two apart.
8.4 The contrary proposition: that the classes coincide
The proposition that the classes coincide, that the NP-complete language admits a polynomial-time deciding algorithm, returns BREAK. It raises no positive warrant on any of the three axes: there is no construction, no polynomial algorithm exhibited for L, no measurement supporting it, and no registrational witness. It therefore fails the externality predicate, which requires at least three pairwise-disjoint positive warrant streams and finds zero, and the operator returns BREAK.
The typing of this BREAK is load-bearing and we state it carefully. BREAK here means absence of positive warrant on every axis, not a demonstration that the coincidence claim is false. The coincidence claim is the negation of the separation, and the standalone separation is routed out of band by Proposition 9.2 rather than established; an operator that does not establish the separation cannot, on pain of contradiction, establish its negation false. So the verdict makes no claim that finding and checking differ in complexity class. Layer one establishes only that finding and checking are distinct operations, and distinct operations may inhabit the same complexity class. The asymmetry between the coincidence claim and the separation is an asymmetry of available warrant, the separation carrying two sealed physical layers and a directional lean while the coincidence claim carries nothing positive, and it is not an asymmetry of established truth value. We do not diagnose the coincidence claim as a zero-magnitude or dimensional degeneracy: such a diagnosis would equivocate operations with complexity classes, it would amount to establishing the separation and so would contradict the separation's open status, and the only encoding that would force it is a degenerate one with a zero-variance row, which the regularity predicate W routes to UNDETERMINED rather than BREAK.
Verdict: BREAK, typed as absence of warrant on every axis, not as a demonstration of falsity.
8.5 The Gate-1 exclusion
One candidate warrant is excluded before the determination, and it is excluded rather than downgraded. The verifying system's own behavior, that it verifies cheaply and generates expensively, is not admitted as warrant for the separation, because its referent is the apparatus performing the audit, and within that apparatus's own bounded operation finding and checking collapse into one walk. By the input gate of Definition 4.6, a proposition whose warrant refers to the auditing apparatus is routed out of band; the apparatus may register external facts but may not use its own operation as evidence. This routing is distinct from, and does not double-count with, the covariate exclusion of the initiating act in Definition 4.7. The two act on different objects by different mechanisms: Definition 4.7 excludes the initiating act as an inadmissible covariate in the dissolution step, a subtraction barred because it would remove the measurement itself, while Definition 4.6 routes a proposition whose warrant is self-referential before any covariate is considered. Should a single physical event be both the initiating act and the apparatus's self-report, it is handled once at the earlier of the two stages, the input gate, and never re-entered as a covariate, so no quantity is removed twice. Relabeling the apparatus's behavior as corroboration does not change its referent and does not lift the exclusion. The witnessed asymmetry of Layer one is sealed on the structural distinctness of the two operations as a general fact, not on the apparatus's self-report, which is why Layer one survives the Gate-1 exclusion while a self-report-based argument would not.
8.6 The determination, stated as one finding
The four verdicts together are the determination. The witnessed asymmetry seals at witness grade. The thermodynamic floor seals at theorem grade and is fenced, barring physical brute-force parallel search without reaching the universal. The universal separation is under-determined and directional. The coincidence claim breaks for want of any positive warrant stream, typed as absence of warrant rather than as established falsity. The proposition that the classes are separate therefore stands strictly above the proposition that they coincide, the one carrying two sealed layers and a directional third, the other carrying no positive warrant on any axis. The asymmetry between the two verdicts comes entirely from the evidence each can muster under identical handling, not from differential treatment, and it is an asymmetry of warrant rather than of established truth. The single most important fact in the determination is that the three layers of the separation are divided by exactly one premise, that the lower two seal and the third does not, and that the divider is the conjecture, which is why the determination is a precise localization rather than either a proof or a bare uncertainty.
9. THE OPERATOR'S VERDICT, AT ITS EARNED STRENGTH
This section states what the verification operator of Section 4 returns on the separation proposition. We treat two propositions separately: the separation with the bridge C admitted as warrant on the structural axis, and the standalone universal separation with no such admission.
Lemma 9.1 (consistency under the admitted premise). Hand the operator the separation proposition for L with C admitted as structural warrant. Then the operator returns SEAL, and the content of that return is consistency under the admitted premise together with linear non-degeneracy of the encoding, not a three-fold discriminating certification of the separation.
Proof. We check the clauses of Definition 4.5 and state precisely what each contributes. The structural axis carries warrant, but the warrant it carries is C admitted, which by Theorem 6.2 is the conjecture; the axis discriminates the separation from its negation only because the conjecture has been admitted on it. The empirical axis records the exponential resource cost of the algorithms actually executed, a cost identical in the world where the separation holds and the world where it fails but no polynomial algorithm has yet been found; it is truth-invariant across the separation and its negation and discriminates neither. The registrational axis records the conviction-without-capacity gap of an observer who verifies a witness but cannot generate one; it is likewise truth-invariant. Two of the three axes therefore carry no discriminating warrant for the separation. They do not break the cascade, since truth-invariance is consistent with passage and no gate fails, but they certify nothing about the separation's truth. The seal predicate det G greater than zero, on the corrected vertex of Section 4.4, certifies linear non-degeneracy of the encoding: that the three residual rows are linearly independent in the chosen encoding. It is asserted here as a hypothesis on the chosen encoding, namely that the admitted structural row is linearly independent of the two truth-invariant rows; per Section 4.3 this is the encoding-relative linear fact and not a consequence the determinant proves, and in particular it is not functional non-recoverability, which Lemma 4.4e shows the determinant cannot deliver. The regularity predicate holds on the well-posed encoding. Therefore S returns SEAL. The return certifies that the operator does not break when handed the premise and that the encoding is linearly non-degenerate. It does not certify the separation, whose entire discriminating warrant sits in the admitted premise C and not in the operator's geometry. ∎
Lemma 9.1 has the operator perform a consistency check, not a certification. The truth-invariance of the two axes, which bounds the operator's warrant, is made precise as follows. Let H denote the indicator of the separation, H = 1 in the world where P ≠ NP and H = 0 in the world where P = NP but no polynomial algorithm has yet been exhibited. Let v_E be the empirical-axis vector, a deterministic function of the execution traces of the algorithms actually run, and let v_ER be the registrational-axis vector, a function of the verifying system's architecture, its capacity to check against its incapacity to generate.
Proposition 9.1a (the two axes are non-discriminating). The vectors v_E and v_ER take identical values under H = 0 and H = 1, hence carry zero mutual information with the truth of the separation:
I(v_E ; H) = 0 and I(v_ER ; H) = 0.
Proof. We compute the mutual information from its definition in terms of Shannon entropy, I(v_E ; H) = H(v_E) − H(v_E | H), where H(v_E) = −Σ_x P(v_E = x) log₂ P(v_E = x) and H(v_E | H) is the conditional entropy. The empirical vector v_E is a deterministic function of the execution traces of the algorithms actually run, and the execution trace of any fixed algorithm A on input x is determined by A and x alone, not by whether a faster algorithm exists, unexecuted, elsewhere in the space of all algorithms. Holding the execution history fixed, the set of algorithms run is the same under both hypotheses, so the distribution of v_E is invariant under H,
P(v_E = x | H = 0) = P(v_E = x | H = 1) = P(v_E = x).
The conditional entropy then collapses to the marginal,
H(v_E | H) = P(H=0) H(v_E | H=0) + P(H=1) H(v_E | H=1) = P(H=0) H(v_E) + P(H=1) H(v_E) = H(v_E) (P(H=0) + P(H=1)) = H(v_E),
since the two probabilities sum to one. Substituting, I(v_E ; H) = H(v_E) − H(v_E) = 0. The registrational vector v_ER is a function of the verifier's check-cheap, generate-costly architecture, a fixed property of the apparatus unchanged by the truth value of a statement about the complexity classes, so the identical argument gives I(v_ER ; H) = 0. The conditioning on a fixed execution history is necessary: unconditionally, a world in which P = NP would over time make the discovery of a fast algorithm more likely, so the invariance is asserted at a horizon at which no polynomial decider for L has been run. ∎
The separation-content lives entirely in C, carried on the structural axis; the two remaining axes are constant across the hypotheses and add nothing that discriminates the separation from its negation. The cascade confirms that admitting C produces no internal contradiction and that the encoding is linearly non-degenerate by Lemma 4.4a; it adds no independent warrant for the separation, because by Proposition 9.1a the two axes that could have added it are uninformative about it. The seal of Lemma 9.1 is therefore a seal of consistency and linear non-degeneracy; a seal on the separation would overstate it, since the separation rides on the admitted conjecture and not on the three-axis convergence. The tri-layer determination reaches the same fact from the other side: two of the three axes are truth-invariant across the separation, so what any seal here certifies is encoding non-degeneracy under the premise, not a discriminating three-fold convergence.
Proposition 9.2 (the standalone universal is routed out of band). Hand the operator the standalone universal separation, with no admission of C. Then the operator does not return SEAL, does not return BREAK, and does not return UNDETERMINED. It routes the proposition out of band by the input gate of Definition 4.6.
Proof. The only warrant that would seal the standalone universal is a premise establishing that no polynomial algorithm decides L, which is C, which by Theorem 6.2 is the universal separation itself. Offering C as warrant for the separation is offering a premise logically equivalent to the conclusion, the conclusion-dependency condition of Definition 4.6. The input gate therefore routes the proposition out of band: the operator refuses to adjudicate the separation on warrant equivalent to the separation. This is not BREAK, since no gate-internal contradiction is found and the geometry is not degenerate; the cascade is declined before evidence is sought. It is not UNDETERMINED, since the regularity predicate W does not fail; UNDETERMINED is reserved strictly for numerical ill-conditioning by Definition 4.5, and the standalone universal raises no conditioning failure. Relabeling C as corroboration does not change that C is equivalent to the conclusion and does not lift the routing. ∎
We keep apart two things a single word would conflate. The operator's UNDETERMINED is a numerical-conditioning verdict and is not in play here. The epistemic status of the standalone universal, as a question about the world, is the separate matter reported in Section 8.3: open, with a directional lean supplied by the structural landscape. The operator routes the standalone universal out of band; the world leaves it open with a lean. These are two statements in two registers, and we do not let them wear one word.
Taken together, Lemma 9.1 and Proposition 9.2 fix the operator's role exactly. Handed the conjecture as a premise, the operator confirms consistency and non-degeneracy and seals on that limited content. Not handed it, the operator declines the separation as conclusion-dependent. In neither case does the operator supply warrant for the separation that the premises did not already contain. This is the operator at its earned strength, and it is precisely what the localization of Section 6 predicts: the separation-content is in the bridge, the bridge is the conjecture, and no apparatus that does not already contain the conjecture can certify the separation.
10. A WORKED INSTANCE OF THE OPERATOR
To make the apparatus concrete and checkable, we exhibit a small explicit encoding and compute every quantity the operator uses. The numbers are illustrative of the structure, not measurements of nature; their role is to show the determinant, the stability margin, and the degeneracy diagnosis as arithmetic a reader can reproduce.
Take N = 4 evidence columns and the three standardized residual rows
r₁ = (1.00, 0.00, −0.50, 0.20), r₂ = (0.10, 1.00, 0.30, −0.40), r₃ = (−0.30, 0.20, 1.00, 0.50).
The Gram matrix G = M̃ M̃ᵀ has entries Gᵢⱼ = ⟨rᵢ, rⱼ⟩, giving approximately
G ≈ [ [1.290, −0.130, −0.700], [−0.130, 1.260, 0.270], [−0.700, 0.270, 1.380] ].
Its determinant is det G ≈ 1.557, strictly positive, so by Lemma 4.4a the three axes are linearly independent and the seal predicate holds. The eigenvalues of G are approximately λ₁ ≈ 2.13, λ₂ ≈ 1.18, λ₃ ≈ 0.62, with product equal to det G as required. By Lemma 4.4b the stability margin is λ_min ≈ 0.62: the verdict SEAL persists under any symmetric Gram perturbation of spectral norm below 0.62, and the determinant stays above (0.62 − ‖E‖₂)³ on that range. The Cauchy-Binet identity gives the same determinant as the sum of squared three-by-three minors over the four column triples, det G = Σ_S (det M̃_S)², which a reader can verify term by term.
Now contrast a degenerate encoding in which the empirical and registrational axes have been built from the same truth-invariant quantity, so that one row is a linear combination of another. Replace r₃ by r₃′ = 2 r₂, leaving r₁ and r₂ unchanged. The three rows now span only a two-dimensional space, every three-by-three minor of the new M̃ vanishes, and det G = 0 by Lemma 4.4a. The operator returns BREAK on the geometry, correctly refusing to certify a three-fold convergence where only two independent axes are present. This is the arithmetic shadow of Proposition 9.1a: when two axes carry the same content, the volume collapses and the determinant reports it. The seal is available only when the three axes are genuinely independent, and the margin λ_min measures how far the encoding stands from the collapse.
The worked instance illustrates the division the paper insists on. A positive determinant with a healthy margin certifies linear non-degeneracy of the encoding, the fact Lemma 4.4a and Lemma 4.4b establish. It does not certify the separation, whose warrant, in the admitted-premise case of Lemma 9.1, sits entirely on the structural axis and not in the geometry, and whose two other axes are, by Proposition 9.1a, the same under the separation and its negation.
11. THE CONSOLIDATED VERDICT
The determination, the operator's earned-strength verdict, and the bridge result consolidate into a single picture. Two contradictory propositions receive structurally asymmetric verdicts produced by one fixed operator under one fixed discipline. The proposition that the classes coincide breaks for absence of any positive warrant on every axis, a verdict typed as absence of warrant rather than as established falsity. The proposition that the classes are separate resolves into three layers that do not share a fate: the witnessed asymmetry and the per-transition thermodynamic floor seal at their honest grades, while the universal separation is sealed only as consistency under the admitted bridge and is otherwise routed out of band, its epistemic openness directional. The bridge conditional, that the no-shortcut premise entails the separation, seals as the logical identity Theorem 6.2 establishes. The table is the terminal consolidation.
| Proposition / Layer | V_F | V_E | V_ER | Verdict |
|---|---|---|---|---|
| P = NP | no warrant | no warrant | no warrant | [X] BREAK, absence of warrant |
| P ≠ NP · Layer 1 witnessed asymmetry | — | — | registers gap | [⟀] sealed, witness grade |
| P ≠ NP · Layer 2 per-transition floor, parallel-search bar | barrier-count | per-crossing floor | — | [⟀] sealed, theorem grade, scope-fenced |
| P ≠ NP · Layer 3 universal, standalone | inductive lean | truth-invariant | truth-invariant | [⟀] consistency under C · [?] without · routed out-of-band by input gate |
| Bridge C → universal separation | entailment-grade | — | — | [⟀] logical identity, C ⟺ P≠NP |
The table is read as follows. The coincidence claim returns BREAK for want of any positive warrant stream on any axis, a verdict typed as absence of warrant and not as a demonstration of falsity, since the standalone separation is itself out of band and its negation therefore cannot be shown false. The witnessed asymmetry of Layer one and the thermodynamic floor of Layer two, the latter with its parallel-search bar standing on the state-count bound of Proposition 5.1, seal at their honest grades and do not move with any admissibility posture. Layer three, the standalone universal, is the single posit-sensitive row: handed the no-shortcut bridge C as admitted warrant it returns a seal whose content is consistency under the premise and not a discriminating certification, by Lemma 9.1; not handed C it is routed out of band by the input gate, by Proposition 9.2, since C is the conjecture and would be conclusion-dependent; and the epistemic openness of the universal, with its directional lean, is the separate register of Section 8.3. The bridge conditional seals in the strict sense that it is, by Theorem 6.2, the logical identity that the conjecture entails the conjecture; we mark it as a seal and are exact that what it seals is an identity, not an external warrant. One qualifier carries into the table from Section 9. The non-discrimination of the empirical and registrational axes, Proposition 9.1a, is conditioned on a fixed execution history at a horizon at which no polynomial decider for L has been run, so the consistency SEAL of Lemma 9.1 carries an implicit at-horizon qualifier; the qualifier bears on the operator's bookkeeping, not on the four load-bearing proofs, which are horizon-free. The single most important fact in the table is the structure of the Layer three row: the separation is reached by the operator exactly up to one admitted premise, that premise is the conjecture, and the operator adds no warrant the premise did not contain. Read down the verdict column, the picture is one determination: the coincidence claim broken, two layers of the separation sealed, the universal localized to one irremovable and physically ungroundable premise.
12. A STRUCTURAL CONJECTURE ON SCALE RECURRENCE
We record, and mark clearly as a conjecture and not a theorem, a structural feature suggested by the originating framework. The suggestion is that the verification structure recurs self-similarly across scale, in the sense that a configuration certified at one scale may itself be treated as a domain on which a verification of the same form is defined, and so onward, with the depth of any actually instantiated recurrence bounded by the information capacity of the region in the sense of the Bekenstein bound, while the formal recurrence as a definitional schema is unbounded. We do not exhibit a scale map under which this self-similarity would be an operator identity, and we therefore make no claim that the recurrence is exact or that it is a theorem. We state it as a direction for further work, and we exclude from it any claim of an actually instantiated infinite regress, which the bound on information capacity forbids. The reader should treat this section as a remark, not a result.
13. AN OPTIONAL READING OF THE OPEN EDGE
We record one interpretive reading and mark it as optional. It is used in no proof, and a reader may reject it entirely without affecting any result. The reader uninterested in interpretation may proceed to Section 13.
The bridge conditional holds its antecedent explicit rather than discharging it. Read through the originating framework's account of generative capacity, the held-open antecedent is the live configuration and a discharged one would be the sterile configuration. Recognition is a two-place relation requiring a distance between what recognizes and what is recognized; collapsing that distance to zero, by asserting that the embodied grip on the asymmetry simply is the abstract separation, empties the relation into a tautology that asserts nothing. The seal on the conditional, with the antecedent named and held open, preserves the distance and is the configuration in which the structure remains generative; the discharge of the antecedent into a claimed fact about the standalone universal would be the collapse into emptiness. On this reading the open edge of the universal is not a deficiency but the feature that keeps the structure alive, and the localization of Section 6, which names the gap exactly and declines to close it, is the disciplined form of that openness. The same framework reads the operator's central object, the achieved cancellation of Section 4.4, as a displacement rather than an absence: a zero constituted by the nonzero terms it balances, conserving its constituents rather than annihilating them. These readings are interpretation and are confined to this section.
14. ASSUMPTIONS, GAPS, AND LIMITATIONS
We enumerate the assumptions and the open points, since a verification result that does not state where it can fail is not yet a usable one.
The encoding is not canonical. The operator's verdict depends on the encoding of Definition 4.1, and no canonical encoding is exhibited for any nontrivial domain. The operator is best read as a schema requiring per-domain instantiation, and any application must justify its encoding and demonstrate that the sign of the determinant is stable under perturbation of the entries. This is the principal limitation of the operator, though not of the four proofs, which do not depend on it.
The seal predicate certifies a linear and encoding-relative fact. By Section 4.3, det G greater than zero certifies linear non-degeneracy of the chosen encoding, not the functional non-recoverability the framework's deletion discipline asserts. Functional non-recoverability is a separate modeling assumption wherever it is relied upon, and it is not proven by the determinant. The seal of Lemma 9.1 inherits this limitation: it is a seal of consistency and linear non-degeneracy, nothing stronger.
The mathematical core is elementary. Fact 4.4 is standard linear algebra, and the seal-vertex correction of Section 4.4 is an elementary observation about orthogonality and linear dependence. The operator's value is as a modeling discipline, not as a new theorem of mathematics.
The covariate-admissibility restriction is a stance. Definition 4.7 restricts admissible common factors to those with a measurable physical signature and excludes the initiating act. This is a substantive epistemic position, related to controlling for measured confounders in statistics, and a reviewer may reasonably contest both the restriction to physically signatured factors and the exclusion of the initiating act. We hold the position and mark it contestable.
The gate predicate is schematic. The eleven gate predicates of Definition 4.5, twelve constraints counting the input gate, are stated as a conjunction of admissibility conditions; their full specification for a given domain is not given here, and the conjunctive structure is a design choice. The arguments of Sections 8 and 9 use only the input gate of Definition 4.6 and the fact that no gate fails under the admitted premise.
Proposition 5.1 is a restatement, due to Bekenstein, Margolus and Levitin, Lloyd, and Aaronson, included for completeness.
The directional lean of Layer three is inductive, not demonstrative. The lean toward separation rests on the structural vacancy of a constructive coincidence hand, the directional unanimity of restricted lower bounds, neighboring separations, and the field-wide expectation. None of these closes the universal, and we do not present the lean as more than an inductive direction on an open question.
The scale recurrence of Section 12 is a conjecture without a defined scale map.
No metaphysical claim is load-bearing. The body uses only the physical-resource bounds of Section 5 and the elementary linear algebra of Section 4. The framework's interpretive commitments, including the reading of Section 13 and any monistic reading of the underlying physics, are confined to Appendix A and are used in no proof.
No claim on the standalone conjecture. We do not claim progress on P versus NP. Theorem 6.2 identifies the bridge as the conjecture; Theorem 7.1 and Proposition 7.2 prove the bridge has no physical discharge; the determination seals the lower two layers and leaves the universal under-determined; the operator confirms consistency under the bridge and declines the standalone universal as conclusion-dependent. At no point is the standalone separation established, and it remains open with a directional lean.
15. RELATED WORK
The physical limits to computation are due to Bremermann, Bekenstein, Margolus and Levitin, and are synthesized by Lloyd; the quantum speed limit is due to Mandelstam and Tamm and to Margolus and Levitin. The question whether physical processes, quantum, adiabatic, relativistic, or analog, can solve NP-complete problems with feasible resources is surveyed by Aaronson, whose conclusion, that they cannot and that this does not bear on the abstract conjecture, is the conclusion this paper formalizes and consolidates. The barriers to proving P versus NP are due to Baker, Gill, and Solovay for relativization, to Razborov and Rudich for natural proofs, and to Aaronson and Wigderson for algebrization; the physical-resource argument falls under relativization. The reversibility of computation is due to Bennett, and the thermodynamic cost of irreversible operations to Landauer, confirmed experimentally by Bérut and colleagues. The hardness of spin-glass ground-state problems is due to Barahona, and the dichotomy for Boolean constraint satisfaction to Schaefer. The use of a Gram determinant as a measure of the independence and the spanned volume of a set of vectors is standard. The Cauchy-Binet form of the Gram determinant, as a sum of squared minors, is classical and is found in Gantmacher. The characterization of the smallest singular value as the distance to the nearest lower-rank matrix is the Eckart-Young theorem, and the one-Lipschitz dependence of symmetric eigenvalues on the matrix is Weyl's inequality; together these supply the stability statement of Lemma 4.4b. The formalization of non-discrimination as vanishing mutual information follows the standard definition of mutual information in Cover and Thomas. The covariate-residualization step is the linear-algebraic form of controlling for a common factor, familiar from partial correlation and the analysis of confounding. The verification operator's three-axis structure and its origin are described in Appendix A.
16. CONCLUSION
We have corrected the verification operator at its seal vertex so that the seal predicate denotes a real object, and stated at the point of definition that the predicate certifies linear non-degeneracy of the encoding rather than a stronger functional independence. We have restated the embodied search-verify asymmetry at its correct strength, resting on operation and state counts and not on dissipation. We have given the tri-layer determination of the search-verify question under one fixed operator: the witnessed asymmetry sealed at witness grade, the per-transition thermodynamic floor sealed at theorem grade and scope-fenced, the universal separation under-determined and directional, and the coincidence claim breaking for absence of warrant on every axis, typed as absence of warrant rather than as a demonstration of falsity. And we have proved the consolidating result. The inference that would carry the embodied asymmetry to the universal separation is a single named premise, the no-shortcut bridge, that bridge is over an NP-complete language logically equivalent to the conjecture, and the bridge cannot be discharged from the physical side, universally because any such discharge would prove the conjecture and sharply for the counting-type bounds because they relativize and are blocked. The operator's verdict is stated at its earned strength: handed the bridge it confirms consistency and non-degeneracy and seals on that limited content; not handed it, it routes the standalone universal out of band as conclusion-dependent, the epistemic openness of the universal being a separate matter the operator does not pronounce.
The consolidated picture is a measurement and two impossibility facts about what was measured. The distance between a real physical fact and the abstract separation of complexity classes is one premise wide; the premise is the conjecture; and the premise has no physical foundation. This is bolder than a claimed proof and more durable, because it cannot be overturned by any future physical instrument: the gap it names is the conjecture, and the conjecture is not a physical quantity. The proposition that the classes are separate stands strictly above the proposition that they coincide, the first carrying two sealed layers and a directional third, the second breaking for absence of any positive warrant on every axis, typed as absence of warrant rather than as established falsity. We make no claim on the conjecture, we have marked the grade of every claim, and we have enumerated every assumption.
APPENDIX A. PROVENANCE AND INTERPRETATION
This appendix records the originating framework and its interpretive vocabulary, none of which is load-bearing for any result in the body. The reader uninterested in provenance may stop at Section 16.
The operator originates in a framework the author develops under the name Trisduction, a topological and geometric account of epistemic verification organized around three orthogonal warrant axes, a cascade of twelve directed constraints corresponding to the directed edges of a tetrahedron on four vertices, and a three-valued verdict. The three axes of Definition 4.1 are the framework's formal-structural, empirical-thermodynamic, and epistemic-registrational axes. The twelve gates of Definition 4.5 are the framework's gate cascade, and the input gate of Definition 4.6 is its self-reference and conclusion-dependency guard, the same guard that excludes the apparatus's own behavior at the Gate-1 exclusion of Section 8.5. The Gram criterion of Fact 4.4 is the framework's nondegeneracy seal, read geometrically as the three axes enclosing a real volume; the seal-vertex correction of Section 4.4 is the framework's identification of the achieved cancellation with the residualization rather than with an orthogonal vanishing sum, and the framework reads that cancellation as a displacement that conserves its constituents, a made zero rather than an absence. The covariate-residualization of Definition 4.3 with the admissibility restriction of Definition 4.7 is the framework's convergence-dissolution test under its mass mandate, whose bidirectionality, that a massless factor can neither seal nor break, is the framework's own discipline. The three-valued output is the framework's sealed, broken, and under-determined verdict economy, and the strict reservation of the under-determined value for numerical ill-conditioning, with conclusion-dependent propositions routed out of band rather than marked under-determined, is the framework's discipline applied here. The tri-layer determination of Section 8 is the framework's resolved determination of the search-verify question, holding the witnessed asymmetry, the scope-fenced thermodynamic floor, and the under-determined directional universal as three layers with non-collapsible boundaries. The reading of the open edge in Section 13 is the framework's account of generative capacity, its orthogonal fertile logos: the configuration is most generative when the recognizing term and the recognized term are held at a genuine distance rather than collapsed into an identity.
The framework carries the priority-monist thesis, that the continuous physical field is the one fundamental and localized configurations are derivative, as a constitutive commitment. We note for the reviewer that this thesis is contested philosophy, that it is not entailed by the physics it draws on, and that it is assumed nowhere in the body of this paper.
REFERENCES
Aaronson, S. 2005. NP-complete problems and physical reality. ACM SIGACT News.
Aaronson, S., and Wigderson, A. 2009. Algebrization: a new barrier in complexity theory. ACM Transactions on Computation Theory.
Baker, T., Gill, J., and Solovay, R. 1975. Relativizations of the P versus NP question. SIAM Journal on Computing.
Barahona, F. 1982. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General.
Bekenstein, J. D. 1981. Universal upper bound on the entropy-to-energy ratio for bounded systems. Physical Review D.
Bennett, C. H. 1973. Logical reversibility of computation. IBM Journal of Research and Development.
Bremermann, H. J. 1962. Optimization through evolution and recombination. In Self-Organizing Systems.
Bérut, A., Arakelyan, A., Petrosyan, A., Ciliberto, S., Dillenschneider, R., and Lutz, E. 2012. Experimental verification of Landauer's principle linking information and thermodynamics. Nature.
Cook, S. A. 1971. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing.
Cover, T. M., and Thomas, J. A. 2006. Elements of Information Theory, second edition. Wiley.
Eckart, C., and Young, G. 1936. The approximation of one matrix by another of lower rank. Psychometrika.
Gantmacher, F. R. 1959. The Theory of Matrices. Chelsea.
Horn, R. A., and Johnson, C. R. 2013. Matrix Analysis, second edition. Cambridge University Press.
Landauer, R. 1961. Irreversibility and heat generation in the computing process. IBM Journal of Research and Development.
Levin, L. A. 1973. Universal sequential search problems. Problems of Information Transmission.
Lloyd, S. 2000. Ultimate physical limits to computation. Nature.
Mandelstam, L., and Tamm, I. 1945. The uncertainty relation between energy and time in non-relativistic quantum mechanics. Journal of Physics (USSR).
Margolus, N., and Levitin, L. B. 1998. The maximum speed of dynamical evolution. Physica D.
Razborov, A. A., and Rudich, S. 1997. Natural proofs. Journal of Computer and System Sciences.
Schaefer, T. J. 1978. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing.
Schaffer, J. 2010. Monism: the priority of the whole. Philosophical Review.
Weyl, H. 1912. Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen. Mathematische Annalen.