A Formal Proof of the Separation P ≠ NP in Bounded Arithmetic

2025/07/07 by Şimşek, Hazar
Mathematics · #Algebraic Geometry #Algebraic Methods #Bounded Arithmetic #Chow Ring #Complexity Theory #Computer Sciences #FOS: Mathematics #Formal Proof #Logic and Foundations #Mathematics #P vs NP #Physical Sciences and Mathematics #Proof Complexity #Theory and Algorithms

paper · doi:10.17605/osf.io/q8rkf

Abstract

A fully formalized proof of P ≠ NP derived in bounded arithmetic, using Chow ring encodings and contradiction via unbounded semantic invariants.

Related

• A Formal Proof of the Separation P ≠ NP in Bounded Arithmetic
• A Formal Proof of the Separation P ≠ NP in Bounded Arithmetic
• Encoding Peano Arithmetic in a Minimal Fragment of Separation Logic
• A Proof for P =? NP Problem
• On interpretations of bounded arithmetic and bounded set theory