World's most popular travel blog for travel bloggers.

[Answers] Why is the set of perfect squares in P?

, ,
Problem Detail:

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?

1. S. Cook, The P versus NP problem, Online

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.