Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to do a polynomial reduction from problem $A$ to problem $B$. Let $n$ denote the input size of $A$. Is the reduction still polynomial if my reduction algorithm computes the value $n!$ for some reason, but size of the resulting instance of $B$ is still polynomial?

Note: $n!$ can be computed in linear time, if one can multiplicate arbitrary large integers in constant time.

share|improve this question
$n!$ actually has on the order of $n \log n$ digits, so depending on your model of computation it might not be quite linear time. But anyway, it's polynomial in $n$. So why would that prevent the reduction from being polynomial? –  Robert Israel Jul 27 '12 at 17:16
Is it valid to assume that one can multiplicate arbitrary large integers in constant time? –  Croq Jul 27 '12 at 17:45
No, but it one can multiply $m$-digit integers in $m^2$ steps (and, using FFT, in $m^{1+\epsilon}$ steps), which should be fine for your set up. –  David Speyer Jul 27 '12 at 17:48
There ARE dangerous subtleties in this area. If we could compute $n! \mod m$ in time polynomial in $\log n$ and $\log m$, we would get a polynomial time algorithm for factorization. (Note that it doesn't make sense to compute $n!$ itself in time $(\log n)^k$, because the size of the output is $n \log n$, but the output of $n! \mod m$ is only $\log m$ sized, so this hypothetical makes sense.) The idea would be to do a binary search for the first $n$ such that $GCD(n!, m) \neq 1$; that first $n$ would then be a prime factor of $m$. But I don't think you've made this error. –  David Speyer Jul 27 '12 at 17:52
@Croq It really depends on your model of computation. This is a standard assumption for the RAM model. There are significant discrepancies between this model and reality, but it is not an unreasonable choice for studying polynomial reductions. –  Erick Wong Jul 27 '12 at 19:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.