2
$\begingroup$

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?


  1. S. Cook, The P versus NP problem, Online
$\endgroup$
  • 1
    $\begingroup$ Please restrict yourself to only one question per post. Since you have an answer to 1) and 2) is a duplicate, I'm editing to leave only 3). $\endgroup$ – Raphael May 27 '16 at 14:56
  • 1
    $\begingroup$ If you are interested in the analysis of your algorithm, please refer to the reference question and give it a try. Feel free to ask new questions about specific steps you have issues with. $\endgroup$ – Raphael May 27 '16 at 14:58
12
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.