It is proved that the problem of a constant term sign computation in the signature бN₂; +, –, ·, /, ^-&,^-∨с is a polynomial one and after adding the square function to the signature it becomes an NP-hard one. Here N₂ is the set of binary notations of all non-negative integers. Operations ^-& and ^-∨ are bitwise conjunction and bitwise disjunction respectively. The division function / always has the second argument not equals to zero and is used only in the case when the result is integer.

NP-hard problem, class FP, variable-free term in the signature, scheme in the basis

Mathematical problems and theory of numerical methods