Incoming links: NP-intermediate
Discrete logarithm Updated 2025-07-16
An important case is the discrete logarithm of the cyclic group in which the group is a cyclic group.
Integer factorization Updated 2025-07-16
Complexity: NP-intermediate as of 2020:
- expected not to be NP-complete because it would imply NP != Co-NP: cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete#comment104849_169
- expected not to be in P because "could we be that dumb that we haven't found a solution after having tried for that long?
NP-hard cryptosystem Created 2025-06-12 Updated 2025-07-16
This is natural question because both integer factorization and discrete logarithm are the basis for the most popular public-key cryptography systems as of 2020 (RSA and Diffie-Hellman key exchange respectively), and both are NP-intermediate. Why not use something more provenly hard?
- cs.stackexchange.com/questions/356/why-hasnt-there-been-an-encryption-algorithm-that-is-based-on-the-known-np-hard "Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?"
Quantum computers are not expected to solve NP-complete problems Updated 2025-07-16
Only NP-intermediate, which includes notably integer factorization:
- quantumcomputing.stackexchange.com/questions/16506/can-quantum-computer-solve-np-complete-problems
- www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf by Scott Aaronson
- cs.stackexchange.com/questions/130470/can-quantum-computing-help-solve-np-complete-problems
- www.quora.com/How-can-quantum-computing-help-to-solve-NP-hard-problems