This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will have the same answer), find the factorization of $n$. Can this be done in deterministic polynomial time?

Alternately, and slightly weaker: is FACTORIZATION (any of the standard decision-problem versions, perhaps "does $n$ have a prime factor between $a$ and $b$?") in $\text{P}^\text{sopf}$?

I'm essentially trying to prove to myself that sopf($n$) cannot be calculated faster than by factoring $n$, but the problem seems hopeless (unless $\text{FACTORIZATION}\in\text{P}$, in which case it is uninteresting). This is interesting because it seems 'obvious' that there could be no better approach, but I can't think of a way to formalize it that would be true, let alone have a hope to be proved.

Other approaches to this problem would be welcome.

3more comments