Axis Journal of Mathematical Statistics and Modelling
A Rigorous Proof of Pâ NP: Comprehensive Analysis
Abstract
Ararat Petrosyan
This work undertakes a comprehensive and detailed proof of P≠ NP by methodically refuting the Compressibility Hypothesis (CH), which suggests the existence of a polynomial-time function f capable of transforming any satisfiable conjunctive normal form (CNF) formula φ into a polynomial-sized set of assignments that includes at least one satisfying solution. The core of our approach lies in the construction of a self-referential CNF formula φf, specifically tailored for any given f, which we demonstrate to be satisfiable while simultaneously excluding all assignments produced by f(Encode(φf )). This exclusion leads to a direct contradiction with the assumptions of CH, thereby establishing P≠ NP with rigorous mathematical backing.
The proof is developed across multiple dimensions, each contributing to a robust argument: We establish a formal equivalence between CH and P = NP, extending this equivalence to encompass deterministic, nondeterministic, and randomized algorithms [1]. This involves detailed logical derivations that address and resolve ambiguities present in earlier formulations, ensuring that every step is fully formalized and reproducible for independent verification. The equivalence proof is a cornerstone, linking the compressibility concept to the broader P vs NP question with precision. The construction of φf relies on an iterative operator T ⟨f⟩ , which generates the self-referential formula through a process that converges to a fixed point [2]. We provide explicit polynomial bounds for this convergence, supported by numerical examples and small-instance verifications, carefully handling the encoding of CNF formulas to prevent spurious assignments from undermining the exclusion properties. The formula φf is shown to maintain satisfiability while systematically excluding all candidate assignments generated by f [3]. This dual property is rigorously validated through exhaustive analyses of small instances, confirming consistency with theoretical predictions and adherence to all imposed polynomial constraints, with special attention to the threshold n ≥ 4. We conduct a thorough examination of major barriers that have historically obstructed P ≠ NP proofs, including relativization, natural proofs, and algebrization. Each barrier is addressed with precise polynomial bounds and detailed arguments, demonstrating resilience under relativized or algebraically extended scenarios and avoiding the pitfalls associated with natural proof methodologies [4]. This analysis ensures that the fixed-point construction remains valid across diverse computational models. To complement theoretical work, we extend computational simulations to instances with up to n ≤ 10000 variables, utilizing Python with the PySAT framework. These experiments verify the correctness of the fixed-point construction, confirm the anticipated O(n5 ) runtime complexity, and provide empirical data showing that the exclusion property holds uniformly across high- dimensional CNF spaces. The scalability of the approach is predictable, with results documented in detail [5]. Finally, we address all methodological gaps identified in prior reviews, including ambiguities in equivalence proofs, guarantees of fixed-point termination, and the resilience against complexity barriers [6]. Detailed Lean code and pseudocode are provided to ensure reproducibility, allowing independent researchers to verify each claim. The methodology seamlessly integrates theoretical reasoning with practical implementation, offering a holistic approach to the problem.
The proof synthesizes theoretical rigor with empirical evidence, employing symbolic reasoning, formal verification in Lean, and extensive numerical simulations. This multifaceted strategy provides a solid foundation, though further validation through independent scrutiny remains a valuable next step.