KIAM Main page Web Library  •  Publication Searh  Русский 

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
Publication language: russian,  pages: 4 (p. 125-128)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Kosovskiy N.K.,  ,  Санкт-Петербургский государственный университет
  • Kosovskaya T.M.,  ,  Санкт-Петербургский государственный университет