Начнем с определения диофантова инварианта $\tau$ из теории сложности. Программой для полинома $f \in \mathbb{Z}[t]$ от одной переменной с целочисленными коэффициентами является объект $\left(1, t, u_{1}, \ldots, u_{k}\right)$, где $u_{k}=f$ и для всех $\ell$, $u_{\ell}=u_{i} \circ u_{j}, i, j<\ell$, о означает,+- или $\times$, а $u_{0}=t, u_{-1}=1$. Тогда $\tau(f)$ – минимум $k$ по всем таким программам.

Является ли количество различных целых нулей $f$ полиномиально ограниченным $\tau(f)$ ? Другими словами, выполняется ли
\[
Z_{\alpha}(f) \leqslant \tau(f)^{c}, \quad f \in \mathbb{Z}[t],
\]

где $Z_{\alpha}(f)$ – количество различных целых нулей $f$, а $c$ – универсальная постоянная.

Эту проблему указали мы с Майком Шубом во время изучения теории сложности. Мы доказали, что утвердительный ответ означает трудноразрешимость теоремы о нулях над $\mathbb{C}$ и, таким образом, $P
eq N P$ над $\mathbb{C}$. См. [54], а также [5].

Поскольку степень $f$ меньше или равна $2^{\tau+1}, \tau=\tau(f)$, то количество нулей не больше, чем $2^{\tau+1}$.

Для полиномов Чебышева количество различных вещественных нулей возрастает экспоненциально по $\tau$.

Во многих классических диофантовых задачах рассматриваются две или более переменные. В данной задаче переменная только одна и, тем не менее, она представляется не такой уж легкой.

Приведем задачу, связанную с только что рассмотренной. Программой для целого $m$ является объект $\left(1, m_{1}, \ldots, m_{\ell}\right)$, где $m_{\ell}=m, m_{0}=1, m_{q}=$ $=m_{i} \circ m_{j}, i, j<q$ и $\circ=+,-$ или $\times$. Определим $\tau(m)$ как минимум $\ell$ над всеми такими программами. Таким образом, $\tau(m)$ представляет кратчайший способ получения целого $m$, начиная с единицы, используя плюс, минус и умножение.

Проблема: Существует ли постоянная $c$, такая что $\tau(k !) \leqslant(\log k)^{c}$ для всех целых $k$ ? Можно ожидать, что это окажется неверным, так что $k$ ! «трудно вычислимо» (см. [54]).