Computable function in polynomial time

Question

Given $m, n$ natural numbers in the binary notation. How can we prove that the function $f(n,m)=[n^{1/m}]$ is computable in polynomial time?

Answer 1

Here is an algorithm that runs in $O(n^4)$ times. This is definitely not the most efficient algorithm but serves as a useful proof that a polynomial algorithm exists.

---

First, check if

$$m>2n>\frac{\ln(n)}{\ln(2)}$$

(this step can clearly be done in $O(n)$ time just based on the number of binary bits in memory each number $n$ and $m$ takes). If so

$$n^{1/m}<n^{\frac{\ln(2)}{\ln(n)}}=2$$

which implies

$$f(n,m)=\lfloor n^{1/m}\rfloor =1$$

If $m\leq 2n$, then note that

$$f(n,m)=\lfloor n^{1/m}\rfloor\leq n^{1/m}<\lfloor n^{1/m}\rfloor+1=f(n,m)+1$$

$$\Rightarrow f(n,m)^m\leq n<(f(n,m)+1)^m$$

Thus, in order to find $f(n,m)$ it is sufficient to find some natural $k_0$ such that $k_0^m\leq n<(k_0+1)^m$. But this is easy, simply iterate through the natural numbers $k\in \{1,2,3,...,n\}$ and test whether they satisfy the condition above. This can be done in polynomial time as multiplication can be done in $O(k^2)$ time and therefore testing whether $k$ satisfies the condition can be done in $O(mk^2)$. Since $k\leq n$, and we have to perform this action at most $n$ times, we can get a final bound of $O(mn^3)$ for this algorithm. Using the fact that $m\leq 2n$ gives us the final bound of $O(n^4)$.

Example: For $m=2$ and $n=5$ (obviously $m=2<10=2n$), we have that

$$k=1: 1^2=1\text{ and }(1+1)^2=4$$ $$k=2: 2^2=4\text{ and }(2+1)^2=9$$ $$k=3: 3^2=9\text{ and }(3+1)^2=16$$ $$k=4: 4^2=16\text{ and }(4+1)^2=25$$ $$k=5: 5^2=25\text{ and }(5+1)^2=36$$

Thus, we get that $f(n,m)=2$.