Lemmy: Bestiverse
  • Communities
  • Create Post
  • Create Community
  • heart
    Support Lemmy
  • search
    Search
  • Login
  • Sign Up
RSS BotMB to Hacker NewsEnglish · 1 day ago

Team claims to have Lean 4 proof that P≠NP

arxiv.org

external-link
message-square
0
fedilink
  • cross-posted to:
  • tech@programming.dev
6
external-link

Team claims to have Lean 4 proof that P≠NP

arxiv.org

RSS BotMB to Hacker NewsEnglish · 1 day ago
message-square
0
fedilink
  • cross-posted to:
  • tech@programming.dev
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.

Comments

alert-triangle
You must log in or register to comment.

Hacker News

hackernews

Subscribe from Remote Instance

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: !hackernews@lemmy.bestiver.se
lock
Community locked: only moderators can create posts. You can still comment on posts.

Posts from the RSS Feed of HackerNews.

The feed sometimes contains ads and posts that have been removed by the mod team at HN.

Visibility: Public
globe

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

  • 457 users / day
  • 1.65K users / week
  • 3.68K users / month
  • 9.55K users / 6 months
  • 2 local subscribers
  • 2.86K subscribers
  • 34.2K Posts
  • 14.8K Comments
  • Modlog
  • mods:
  • patrick
  • RSS Bot
  • BE: 0.19.5
  • Modlog
  • Instances
  • Docs
  • Code
  • join-lemmy.org