1
$\begingroup$

This is an assignment of an introductory course of complexity theory and I need to find a way to do the following:

Given $n,m \in \Bbb N$, is $n \le m!$ ?

The idea is to provide a Post Machine that can decide this in an efficient way, using $n,m$ in a binary codification.

We know that the factorial isn't efficient, so the problem actually is just to find a way to decide this, if it's possible.

I know how to compare if $n\le m$, but the factorial is my problem. I don't how how to compute $m!$ with a Post Machine, if possible, in polynomial-time.

I guess that the most simple way to do this is comparing $n$ with factorials of numbers that are lower than $m$, but the factorial it's still my problem.

My question, is there an algorithm that can help me?

$\endgroup$
  • $\begingroup$ What kind of "efficient" to you need here? Polynomial-time? $\endgroup$ – Raphael Apr 2 '14 at 20:45
  • 1
    $\begingroup$ Anyway, this is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. If you are uncertain how to improve your question, why not ask in Computer Science Chat? $\endgroup$ – Raphael Apr 2 '14 at 20:46
  • $\begingroup$ Hint: do you actually need compute $m!$ in order to decide? $\endgroup$ – Raphael Apr 2 '14 at 20:47
  • $\begingroup$ I've edited the question and yes, I need to compute $m!$. Sorry for the poor explanation. $\endgroup$ – joanca Apr 2 '14 at 21:22
  • 1
    $\begingroup$ Hint: try instead to find whether $\log n \leq \log m!$. $\endgroup$ – Yuval Filmus Apr 2 '14 at 21:35
4
$\begingroup$

Here is a different solution than the one I suggested in the comments. Compute the sequence of factorials $1!,2!,3!,4!,\ldots$ until you get a number which is at least $n$. Since $(k+1)!/k! = O(\log (k!))$, you only compute numbers of magnitude $O(n\log n)$ and so of length $(1+o(1))|n|$ (here $|n|$ is the length of $n$ encoded in binary). Having found the least $k$ such that $n \leq k!$, we know that $n \leq m!$ iff $m \geq k$.

Since the sequence of factorials grows so fast, the running time isn't too bad — it's quasilinear in $|n|$ (at least in the RAM model). I'll let you work that out.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.