Complexity of Boolean functions and Boolean function systems realization in a base consisting of all monotone functions and a finite number of non-monotone functions is researched. The weight of any monotone function in the base is supposed to be 0, the weight of non-monotone function in it is positive. A. A. Markov studied special case of this base, where the non-monotone part consisted of the negation function. He showed that the minimum number of negation elements which are needed to realize an arbitrary function / equals |"log2(d(f) + 1)]. Here d(f) is the maximum number of value changes from 1 to 0 over all increasing chains of arguments tuples. The aim of this paper is to prove that the complexity of a Boolean function / realization equals Pl~log2(d(f) + 1)] - O(1), where p is the minimum weight of non-monotone elements in the base. Similar generalization of the classical Markov's result concerning the realization of Boolean function systems is obtained too.
Download file
Counter downloads: 261
- Title On the complexity of circuits in bases containing monotone elements with zero weights
- Headline On the complexity of circuits in bases containing monotone elements with zero weights
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(30)
- Date:
- DOI
Keywords
булевы схемы, схемы из функциональных элементов, базисы с нулевыми весами, сложность булевых функций, схемная сложность, инверсионная сложность, теорема Маркова, Boolean circuits, logic circuits, bases with zero weight elements, Boolean function complexity, circuit complexity, inversion complexity, Markov's theoremAuthors
References
Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.
Сэвидж Д. Е. Сложность вычислений. М.: Факториал, 1998.
Гилберт Э. Н. Теоретико-структурные свойства замыкающих переключательных функций // Кибернетический сборник. Вып. 1. М.: ИЛ, 1960. C. 175-188.
Марков А. А. Об инверсионной сложности систем функций // Докл. АН СССР. 1957. Т. 116. №6. С. 917-919.
Марков А. А. Об инверсионной сложности систем булевых функций // Докл. АН СССР. 1963. Т150. №3. С. 477-479.
Нечипорук Э. И. О сложности схем в некоторых базисах, содержащих нетривиальные элементы с нулевыми весами // Проблемы кибернетики. Вып. 8. М.: Физматгиз, 1962. C. 123-160.
Нечипорук Э. И. О сложности схем в некоторых базисах, содержащих нетривиальные элементы с нулевыми весами // Докл. АН СССР. 1961. T. 139. №6. С. 1302-1303.
Нечипорук Э. И. О сложности суперпозиций в базисах, содержащих нетривиальные линейные формулы с нулевыми весами // Докл. АН СССР. 1961. T. 136. №3. С. 560-563.
Kochergin V. V. and Mikhailovich A. V. Some extensions of the inversion complexity of Boolean functions. Cornell University Library, 2015. http://arxiv.org/abs/1506.04485.
Morizumi H. Limiting negations in formulas // LNCS. 2009. V. 5555. P. 701-712.
Fischer M. J. The complexity of negation-limited networks -a brief survey // LNCS. 1975. V. 33. P. 71-82.
Tanaka K., Nishino T., and Beals R. Negation-limited circuit complexity of symmetric functions // Inf. Proc. Lett. 1996. V. 59. No. 5. P. 273-279.
Sung S. and Tanaka K. Limiting negations in bounded-depth circuits: an extension of Markovs theorem // LNCS. 2003. V. 2906. P. 108-116.
Morizumi H. and Suzuki G. Negation-limited inverters of linear size // IEICE Trans. Inform. and Systems. 2011. V.E93-D. No. 2. P. 257-262.
Guo S., Malkin T., Oliveira I. C., and Rosen A. The power of negations in cryptography // LNCS. 2015. V. 9014. P. 36-65.
Jukna S. Boolean Function Complexity. Advances and Frontiers. Berlin; Heidelberg: Springer, 2012. 620 p.
On the complexity of circuits in bases containing monotone elements with zero weights | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 4(30).
Download full-text version
Counter downloads: 775