KIAM Main page Web Library  •  Publication Searh   
Publication

Article collection "Mathematical Problems of Cybernetics" 16, Moscow, 2007
Authors: Kosovskiy N.K., Kosovskaya T.M.
Polynomiality and NP-hardness of the constant terms sign computation problem
Abstract:
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.
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
Source text: