Discussion
Loading...

Post

  • About
  • Code of conduct
  • Privacy
  • Users
  • Instances
  • About Bonfire
Hacker News
@h4ckernews@mastodon.social  ·  activity timestamp 5 days ago

Team claims to have Lean 4 proof that P≠NP

https://arxiv.org/abs/2510.17829

#HackerNews #PvsNP #Lean4 #Proof #Mathematics #ComputerScience #HackerNews

arXiv.org

A Homological Proof of $\mathbf{P} \neq \mathbf{NP}$: Computational Topology via Categorical Framework

This paper establishes the separation of complexity classes $\mathbf{P}$ and $\mathbf{NP}$ through a novel homological algebraic approach grounded in category theory. We construct the computational category $\mathbf{Comp}$, embedding computational problems and reductions into a unified categorical framework. By developing computational homology theory, we associate to each problem $L$ a chain complex $C_{\bullet}(L)$ whose homology groups $H_n(L)$ capture topological invariants of computational processes. Our main result demonstrates that problems in $\mathbf{P}$ exhibit trivial computational homology ($H_n(L) = 0$ for all $n > 0$), while $\mathbf{NP}$-complete problems such as SAT possess non-trivial homology ($H_1(\mathrm{SAT}) \neq 0$). This homological distinction provides the first rigorous proof of $\mathbf{P} \neq \mathbf{NP}$ using topological methods. The proof is formally verified in Lean 4, ensuring absolute mathematical rigor. Our work inaugurates computational topology as a new paradigm for complexity analysis, offering finer distinctions than traditional combinatorial approaches and establishing connections between structural complexity theory and homological invariants.
  • Copy link
  • Flag this post
  • Block
Log in

bonfire.cafe

A space for Bonfire maintainers and contributors to communicate

bonfire.cafe: About · Code of conduct · Privacy · Users · Instances
Bonfire social · 1.0.0-rc.3.21 no JS en
Automatic federation enabled
  • Explore
  • About
  • Members
  • Code of Conduct
Home
Login