4
$\begingroup$

I've been reading up a lot Prime Factorization and it's complexity, including a fair number of questions on this very site. However, I still feel there is a question still left unanswered.

So, basically, there is the "Decision Variant" of the Integer Factorization Problem, as it's officially known, as well as the "Function Variant". The "Decision Variant" simply asks whether a given integer n has a factor greater than 1. The "Function Variant", on the other hand, concerns itself with actually finding the Prime Factors if there is more than 1 (it being equivalent to the "Decision Variant" if the answer to that is 'no').

When the question is asked "In what complexity class does Integer Factorization lie", the answer given is usually along the lines of: "The Decision Variant is both in NP and in Co-NP". That is great to know, but that question has been answered and does therefore not need answering again. I will therefore make my Question more specific.

Question: Is it known in what Complexity Class the "Function Variant" of the Integer Factorization Problem, aka the Prime Factorization Problem, lies? If so, what class would that be?

Improve this question
$\endgroup$
1
  • $\begingroup$ Let F_n be the set of positive integers having precisely n prime facfors, counted with multiplicity. For n=1, F_n has a polytime algorithm to decide if a number is in that set or not. For n larger than 1, no such fast algorithm is currently known. $\endgroup$ Commented Mar 21, 2015 at 7:03

1 Answer 1

Reset to default
3
$\begingroup$

Factoring is best thought of as defining a complexity class on its own. However, to put it in the context of commonly studied classes of NP search (function) problems: it is proved in this paper of mine that integer factoring has a randomized polynomial-time reduction to PPA and PPP (even a variant of PPP corresponding to the weak pigeonhole principle). Assuming the Riemann hypothesis for $L$-functions of quadratic Dirichlet characters, both reductions can be derandomized, putting factoring in PPA and in $\mathrm{FP^{PPP}}$. It is an open problem whether factoring is in PPAD.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.