Does there exist a two variable polynomial $P(X,Y)$ with integer coefficients such that a positive integer $n$ is a perfect square iff there do not exists a tuple $(X,Y)$ of positive integers such that $P(X,Y)= n$ ?
Spoiler:
There does exists a three variable polynomial $P(X,Y,Z)$ such that an integer $n$ is a perfect square iff there do not exists a tuple $(X,Y,Z)$ of positive integers such that $P(X,Y,Z) = n$. This extremely tricky construction appeared in USA 2013 IMO TST P8 (see the thread for two constructions). On that thread a certain user raises the question about the nonexistence of such polynomial for two-variable cases, but since that's not answered there I'm asking it here.