Иногда эта проблема мне кажется подарком математике со стороны компьютерных наук. Было бы полезно сформулировать ее в виде, который выглядит привычнее для математики.
С этой целью рассмотрим сначала теорему Гильберта о нулях над множеством комплексных чисел. Пусть $f_{1}, \ldots, f_{k}$ – комплексные полиномы от $n$ переменных. Требуется решить, имеют ли они общий нуль $\zeta \in \mathbb{C}^{n}$. Теорема о нулях утверждает, что общего нуля нет тогда и только тогда, когда существуют комплексные полиномы $g_{1}, \ldots, g_{k}$ от $n$ переменных, удовлетворяющие полиномиальному тождеству
\[
\sum_{i=1}^{k} g_{i} f_{i}=1 .
\]
Эффективная теорема о нулях, доказанная Браунуэллом (1987) и другими, утверждает, что в приведенной выше формулировке можно допустить, что степени $g_{i}$ удовлетворяют неравенствам
\[
\operatorname{deg} g_{i} \leqslant \max (3, D)^{n}, D=\max \operatorname{deg} f_{i} \text {. }
\]
С таким ограничением степеней задача разрешимости становится задачей линейной алгебры. При заданных коэффициентах $f_{i}$ можно проверить, имеет ли (1) решение относительно коэффициентов $g_{i}$. Таким образом, мы получаем некоторый алгоритм решения теоремы о нулях. Количество необходимых для решения арифметических шагов возрастает по экспоненте при увеличении количества коэффициентов $f_{i}$ (входных данных).
Гипотеза (над $\mathbb{C}$ ). Не существует алгоритма решения теоремы о нулях, в котором количество арифметических иагов возрастает полиномиально по времени ${ }^{1}$.
Для придания математического смысла этой гипотезе необходимо формальное определение алгоритма. В этом контексте традиционное определение машины Тьюринга не имеет смысла. В работе [6] было предложено удовлетворительное определение, а соответствующая теория создана в [5].
${ }^{1}$ Под возрастанием полиномиально по времени здесь и далее имеется ввиду полиномиальное увеличение количество необходимых для решения арифметических шагов при увеличении входных данных (в данном случае – количества коэффициентов $f_{i}$ ). – Прим. ред.
Очень кратко опишем машину над $\mathbb{C}$. Входные данные, состояние машины и выходные данные представляют собой конечные цепочки комплексных чисел. Вычисления над состояниями включают в себя арифметические операции, сдвиги по цепочке и операции ветвления по условию $x_{1}=0$.
Величина входных данных – это количество элементов во входной цепочке. Время вычислений – количество машинных операций, используемых при переходе от ввода к выводу. Таким образом, полиномиальный по времени алгоритм над $\mathbb{C}$ корректно определен.
Заметим, что все, что было сказано о машинах и о приведенной выше гипотезе, использует только структуру множества $\mathbb{C}$ как поля, и, следовательно, как машины, так и гипотеза могут быть рассмотрены над любым полем. В частности, если полем является $Z_{2}$, состоящее из двух элементов, мы получим машины Тьюринга.
Рассмотрим проблему разрешимости: Рассмотрим $k$ многочленов от $n$ переменных с коэффициентами из $Z_{2}$. Существует ли общий нуль $\zeta \in\left(Z_{2}\right)^{n}$ ?
Гипотеза. Полиномиального по времени алгоритма над $Z_{2}$, разрешающего эту проблему, не существует.
Данная гипотеза является просто новой формулировкой классического предположения $P
eq N P$.
Выше мы не рассмотрели основные идеи и теоремы, относящиеся к $N P$-полноте. Классический случай Кука и Карпа можно найти в [19], а теорию над произвольным полем в [5].
