Skip to main content

On Sale: GamesAssetsToolsTabletopComics
Indie game storeFree gamesFun gamesHorror games
Game developmentAssetsComics
SalesBundles
Jobs
TagsGame Engines

Integer factorization isn't NP-complete

A topic by Chaoseed created Nov 05, 2023 Views: 60 Replies: 1
Viewing posts 1 to 2

Well, it's "generally suspected not to be NP-complete", Wikipedia has a citation. I guess if you proved that it is or is not NP-complete, that would be a significant result...

Host

Fair enough.  I probably should have made that clear in the text.  What I meant was that if you could solve an NP-complete problem fast enough that you could also solve integer factorization problems.  Even though it's probably not NP-complete, it's definitely in NP.