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 aperfect 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?S. Cook, The P versus NP problem, Online
Why is the set of perfect squares in P?
complexity theory;time complexity;polynomial time;number theory
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 $mm=n$. If so, terminate. Otherwise, if $mm>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. 