I am reading an article by Cook [1]. In it he writes:
The set of perfect squares is in P, since Newton's method can be used to efficiently approximate square roots.
I can see how to use Newton's method to decide whether a natural number is a perfect square or not, but it seems tricky to analyse.
Is there an easier way to see that the set of perfect squares is in P?
A simple answer is "binary search". Keep track of a lower bound (starts out with 1) and an upper bound (starts out with $n$). In each iteration compute the midpoint $m$. In polytime check if $m∗m=n$. If so, terminate. Otherwise, if $m∗m>n$ reduce the upper bound to $m$, else increase the lower bound to $m$. If the upper bound and the lower bound become the same and the midpoint squared is not equal to $n$, then $n$ is not a perfect square. This terminates in $\log n$ steps, which is polynomial in the bit size of $n$, i.e., the length of the input. Each iteration runs in polynomial time as well, so the overall algorithm runs in polytime.
