1
$\begingroup$

Let $x$ be a positive integer and let $y$ be a real number such that $$y=\sqrt{x}$$

Objectives:

  1. If $y$ is an integer, find it in polynomial time.

  2. If $y$ is not an integer, prove that there is no integer solution in polynomial time.

Is there any algorithm which can do that?

  • 2
    If you can find the [integer square root](http://en.wikipedia.org/wiki/Integer_square_root) in polynomial time, the you can prove the 2nd objective at the cost of 1 multiplication & 1 comparison: $\lfloor \sqrt{x} \rfloor^2 \stackrel{?}{=} x$. Check the book:$\ $ *A Course in Computational Algebraic Number Theory by H. Cohen*. There might be an algorithm for computing the integer square root.2012-09-01
  • 1
    Apparently this post http://math.stackexchange.com/questions/34235/algorithm-for-computing-square-root-of-a-perfect-square-integer2012-09-01
  • 1
    Don't you want polynomial in $\ln(x)$?2012-09-01

2 Answers 2

3

You could implement some sort of digit-by-digit algorithm. If $n=\log x$, this should involve $O(n)$ arithmetic operations, none of which involve numbers larger than $x$. So the time required will be no worse than $O(n^3)$ or thereabouts; certainly it'll be polynomial in $n$.

0

Simply testing if $x=k^2$ for $k=0, 1, \ldots$ until you hit or exceed $x$. has time $O(\sqrt x)$.

  • 0
    Please, take into account that the input is stored in bits and one multiplication is not one step, but already a polynomial of steps, depending on the input size.2012-09-01
  • 0
    ... and not forgetting that "polynomial" here should mean "polynomial evaluated at $\log x$" or "polynomial in the number of digits of $x$"2012-09-01