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$
6
  • $\begingroup$ What kind of "efficient" to you need here? Polynomial-time? $\endgroup$
    – Raphael
    Apr 2, 2014 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, 2014 at 20:46
  • $\begingroup$ Hint: do you actually need compute $m!$ in order to decide? $\endgroup$
    – Raphael
    Apr 2, 2014 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, 2014 at 21:22
  • 1
    $\begingroup$ Hint: try instead to find whether $\log n \leq \log m!$. $\endgroup$ Apr 2, 2014 at 21:35

1 Answer 1

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.