Может ли разрешимость диофантова уравнения $f(x, y)=0$ (входные данные $-f \in \mathbb{Z}[u, v]$ ) быть определена за время $2^{s^{c}}$, где $c$ — универсальная постоянная?
Здесь $s=s(f)$ — «величина» $f$, определенная следующим образом:
\[
s(f)=\sum_{|\alpha| \leqslant d}\left(\left|a_{\alpha}\right|+1\right), \quad f(x, y)=\sum_{|\alpha| \leqslant d} a_{\alpha} x^{\alpha_{1}} y^{\alpha_{2}}, \quad \alpha=\left(\alpha_{1}, \alpha_{2}\right)
\]

и $|\alpha|=\alpha_{1}+\alpha_{2}, \alpha_{i} \geqslant 0$. Кроме того, функция $f$ считается разрешимой, если существуют целые $x, y$ такие, что $f(x, y)=0$, а также предполагается, что вычисления проводятся с использованием вычислительной машины Тьюринга.

Эта задача, по существу, поставлена в [13]. Величина $s(f)$ — это некоторый вариант «высоты» $f$. Предполагаемые границы высоты, например, как в [31], могут оказаться полезными в разрешении этой задачи. По данной проблеме можно также рекомендовать [36].