Доказывается, что задача вычисления значения знака постоянного терма в сигнатуре бN₂; +, –, ·, /, ^-&,^-∨с полиномиальна. В то же время добавление в эту сигнатуру функции возведения в квадрат превращает эту же задачу (вычисления знака постоянного терма) в NP-трудную. Здесь N₂ – множество двоичных записей неотрицательных натуральных чисел. Операции ^-& и ^-∨ являются поразрядными операциями конъюнкции и дизъюнкции соответственно. Операция деления / всегда имеет второй аргумент, отличный от нуля, и используется только если результат является целым.

NP-трудные задачи, класс FP, постоянный терм в заданной сигнатуре, схема в заданном базисе

Математические вопросы и теория численных методов