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?

$\endgroup$
  • 2
    $\begingroup$ If you can find the 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. $\endgroup$ – user2468 Sep 1 '12 at 16:13
  • 1
    $\begingroup$ Apparently this post math.stackexchange.com/questions/34235/… $\endgroup$ – user2468 Sep 1 '12 at 16:14
  • 1
    $\begingroup$ Don't you want polynomial in $\ln(x)$? $\endgroup$ – i. m. soloveichik Sep 1 '12 at 16:25
3
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Fejwin Sep 1 '12 at 16:07
  • $\begingroup$ ... and not forgetting that "polynomial" here should mean "polynomial evaluated at $\log x$" or "polynomial in the number of digits of $x$" $\endgroup$ – Jyrki Lahtonen Sep 1 '12 at 19:22

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.