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

Abstract:

It is proved that the problem of a constant term sign computation in the signature áN_{2}; +, –, ·, /, ^{-}&,^{-}∨ñ is a polynomial one and after adding the square function to the signature it becomes an NP-hard one.
Here N_{2} 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.

Keywords:

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

Publication language:russian,
pages:4(p. 125-128)

Research direction:

Mathematical problems and theory of numerical methods