4 ms·
My understanding is that factoring is NOT believed to be NP-hard. Can you point to literature that suggests it is? Researchers and professors I've spoken to see
by _asummers 11y ago
My understanding is that factoring is NOT believed to be NP-hard. Can you point to literature that suggests it is? Researchers and professors I've spoken to seem to think it lacks the inherent structure that many NP-complete problems seem to have. My (nonexpert) personal belief is that it will be one of the next problems to fall.
- kirrent 11y agoFactoring is almost certainly not NP-hard. That would mean that NP is contained in BQP which would be a staggering result. While there are some NP problems that are in BQP the idea that somehow NP-complete problems are solvable in polynomial time on a quantum computer seems kinda ridiculous to me. I'd be happy to be proven wrong some time in the future though.