We define an "integer algorithm" as an algorithm that takes integer inputs and produces integer outputs.
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?
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?"
Articles by others on the same topic
The term "inverse problem" generally refers to a type of problem in various fields (such as mathematics, physics, engineering, and data science) where one aims to infer or reconstruct the inputs or causes from observed outputs or effects. Inverse problems contrast with "forward problems," where the relationship between inputs and outputs is known, and the goal is to predict the results of certain input conditions.