I am interested in the complexity theoretic equivalences of prime number factorization. My interest stems from prime number factorization being one of the few candidates for NPI.

I am especially interested to learn wether there are some not initially obvious reductions. Any possible reduction type (Karp, Turing, ...) would be of interest. Im sure there is a lot known already on the subject but i am not sure where to find a good resource on this.

I am aware that PRIME, (i.e. the decision problem that checks wheter a number is prime or not), is in $P$. However, i am interested in the harder problem of finding the explicit factorization, which is in $FNP$. This problem is not known to be in $P$ or $NP-complete$ making it a very interesting candidate for $NPI$ problems. Consequently, any reduction would be interesting for understanding $NPI$

Is there a review article or even better a database that comprehensively lists all known reductions to and from prime number factorization?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.