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?

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