Find $y=\sqrt{x}$ where $x$ and $y$ positive integers in polynomial time? 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?

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