Article collection "Mathematical Problems of Cybernetics" №16, Moscow, 2007
Authors:Kosovskiy N.K., Kosovskaya T.M.
Polynomiality and NP-hardness of the constant term’s sign computation problem
It is proved that the problem of a constant term sign computation in the signature бN2; +, –, ·, /, -&,-∨с is a polynomial one and after adding the square function to the signature it becomes an NP-hard one.
Here N2 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