We don't know that factorization is NP-complete> Show me a reduction from SAT to factorization.
It's kind of trivial to say it's in NP because we can verify in P time, that's not a criticism of you just of the definition!!
I think a better definition of NP is "only nonpoly algos can exist, no P algos can exist". By that definition of NP, we don't even know that it's in NP strictly because there could exist P algorithms for solving it. It's more in 'unknown-NP' if that were a class! hahaha! :)
I always found that part odd. I’d assume you would want the problem you build your crypto system built around to be NP-complete, since that would seem to put you on the firmest possible ground. And yet those are most likely not NP-complete, and I think the post-quantum systems proposed aren’t NP complete either.
Maybe being NP-complete isn’t as important as I realize? Or maybe there’s something about NP-complete problems that make them less amenable to be a valid crypto system?
eru|1 year ago
However, we don't know if these bounds are tight, or whether they are eg in P, or something in between.
keepamovin|1 year ago
It's kind of trivial to say it's in NP because we can verify in P time, that's not a criticism of you just of the definition!!
I think a better definition of NP is "only nonpoly algos can exist, no P algos can exist". By that definition of NP, we don't even know that it's in NP strictly because there could exist P algorithms for solving it. It's more in 'unknown-NP' if that were a class! hahaha! :)
openasocket|1 year ago
Maybe being NP-complete isn’t as important as I realize? Or maybe there’s something about NP-complete problems that make them less amenable to be a valid crypto system?