GoThread
appearance log in
home all local communities
c/tech@programming.dev

Tech

log in to join
follow from another instance

Not on this instance? Enter your own instance's domain to go straight to following c/tech@programming.dev there.

hashtags

#tech
0
c/tech@programming.dev · PhilipTheBucket@piefed.social · 22 Oct 2025 19:58

Team claims to have Lean 4 proof that P≠NP

#tech
arXiv.org A Homological Separation of $\mathbf{P}$ from $\mathbf{NP}$ via Computational Topology and Category Theory 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. 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. arxiv.org

check post at origin

0 comments

0 comments

log in to comment.

about

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

members
3552
posts
32
created
15 Feb 2024
active / week
0
active / month
1

moderators

  • @Vacant@programming.dev

rss · modlog

GoThread · self-hosted threadiverse · instances · modlog · rss · appearance · AGPL-3.0