I am reading an article by Cook . 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?
- S. Cook, The P versus NP problem, Online