pith. sign in
module module high

IndisputableMonolith.Complexity.PvsNPAssembly

show as:
view Lean formalization →

This module assembles the full conditional argument that P ≠ NP in the Recognition Science framework, given a topological obstruction in the J-cost landscape for unsatisfiable SAT instances. Complexity theorists working inside the RS program would cite it as the capstone that stitches circuit lower bounds to the recognition operator. The structure is an import-and-composition assembly that invokes the J-frustration non-naturalness result together with the RSatEncoding to close the gap.

claimConditional on a positive Betti-1 topological obstruction in the J-cost landscape of an unsatisfiable k-CNF formula, the Recognition Science operator $\hat{R}$ yields a non-natural polytime witness for satisfiability, implying $P \neq NP$.

background

The module sits inside the Complexity domain and imports eight supporting modules that develop the P vs NP reduction inside Recognition Science. Key definitions include the J-cost Laplacian on the Boolean hypercube (vertices are assignments, edges weighted by satJCost differences), J-frustration (binary measure 0 for SAT and 1 for UNSAT that quantifies topological depth of the cost barrier), and the RSatEncoding (the operator $\hat{R}$ reaches zero J-cost in O(n) steps for satisfiable instances). NonNaturalness supplies the Razborov-Rudich criteria that J-frustration satisfies to block natural proofs. CircuitLedger and CircuitLowerBound translate these into super-polynomial size lower bounds for any feed-forward Boolean circuit attempting to simulate the global J-cost gradient.

proof idea

This is an assembly module, no proofs. It composes the imported results: the JFrustration and NonNaturalness modules establish the non-natural lower bound, CircuitLowerBound converts high frustration into circuit-size blow-up, and RSatEncoding supplies the contrasting O(n) recognition path for satisfiable formulas, yielding the conditional dissolution of P = NP.

why it matters in Recognition Science

The module completes the P ≠ NP argument conditional on the topological obstruction and is imported by IndisputableMonolith.Core.Complexity to expose the result at the framework level. It directly realizes the core claim stated in the RSatEncoding doc-comment that $\hat{R}$ provides a non-natural polytime certifier for SAT, closing the program outlined in the JCostLaplacian and JFrustration modules.

scope and limits

used by (1)

From the project-wide theorem graph. These declarations reference this one in their body.

depends on (8)

Lean names referenced from this declaration's body.

declarations in this module (8)