Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Может ли разрешимость диофантова уравнения $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].
