Computable function in polynomial time 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?
 A: 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$.
