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

С этой целью рассмотрим сначала теорему Гильберта о нулях над множеством комплексных чисел. Пусть $f_1,\dots ,f_k$ — комплексные полиномы от $n$ переменных. Требуется решить, имеют ли они общий нуль $\zeta \in {\mathbb{C}}^n$. Теорема о нулях утверждает, что общего нуля нет тогда и только тогда, когда существуют комплексные полиномы $g_1,\dots ,g_k$ от $n$ переменных, удовлетворяющие полиномиальному тождеству
$$\sum _{i=1}^k{g}_i{f}_i=1.$$

Эффективная теорема о нулях, доказанная Браунуэллом (1987) и другими, утверждает, что в приведенной выше формулировке можно допустить, что степени $g_i$ удовлетворяют неравенствам
$$\mathrm{deg}{g}_i⩽max(3,D{)}^n,D=max\mathrm{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$, разрешающего эту проблему, не существует.

Данная гипотеза является просто новой формулировкой классического предположения $PeqNP$.

Выше мы не рассмотрели основные идеи и теоремы, относящиеся к $NP$-полноте. Классический случай Кука и Карпа можно найти в [19], а теорию над произвольным полем в [5].