LibreTechni.ca
  • Communities
  • Create Post
  • Create Community
  • heart
    Support Lemmy
  • search
    Search
  • Login
  • Sign Up
PhilipTheBucket@piefed.social to Tech@programming.devEnglish · 9 days ago

Team claims to have Lean 4 proof that P≠NP

arxiv.org

external-link
message-square
0
fedilink
  • cross-posted to:
  • hackernews@lemmy.bestiver.se
1
external-link

Team claims to have Lean 4 proof that P≠NP

arxiv.org

PhilipTheBucket@piefed.social to Tech@programming.devEnglish · 9 days ago
message-square
0
fedilink
  • cross-posted to:
  • hackernews@lemmy.bestiver.se
A Homological Proof of $\mathbf{P} \neq \mathbf{NP}$: Computational Topology via Categorical Framework
arxiv.org
external-link
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.
alert-triangle
You must log in or register to comment.

Tech@programming.dev

tech@programming.dev

Subscribe from Remote Instance

Create a post
You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !tech@programming.dev

A community for high quality news and discussion around technological advancements and changes

Things that fit:

  • New tech releases
  • Major tech changes
  • Major milestones for tech
  • Major tech news such as data breaches, discontinuation

Things that don’t fit

  • Minor app updates
  • Government legislation
  • Company news
  • Opinion pieces

Community Wiki

Visibility: Public
globe

This community can be federated to other instances and be posted/commented in by their users.

  • 8 users / day
  • 8 users / week
  • 8 users / month
  • 8 users / 6 months
  • 0 local subscribers
  • 2.13K subscribers
  • 50 Posts
  • 0 Comments
  • Modlog
  • mods:
  • Vacant@programming.dev
  • BE: 0.19.5
  • Modlog
  • Instances
  • Docs
  • Code
  • join-lemmy.org