Asymptotics of growth for non-monotone complexity of multi-valued logic function systems. (English) Zbl 1386.94119
Summary: The problem of the complexity of multi-valued logic functions realization by circuits in a special basis is investigated. This kind of basis consists of elements of two types. The first type of elements are monotone functions with zero weight. The second type of elements are non-monotone elements with unit weight. The non-empty set of elements of this type is finite.
In the paper the minimum number of non-monotone elements for an arbitrary multi-valued logic function system \(F\) is established. It equals \(\lceil \log_u (d(F) + 1)\rceil - O(1)\). Here \(d(F)\) is the maximum number of the value decrease over all increasing chains of tuples of variable values for at least one function from system \(F\); \(u\) is the maximum (over all non-monotone basis functions and all increasing chains of tuples of variable values) length of subsequence such that the values of the function decrease over these subsequences.
In the paper the minimum number of non-monotone elements for an arbitrary multi-valued logic function system \(F\) is established. It equals \(\lceil \log_u (d(F) + 1)\rceil - O(1)\). Here \(d(F)\) is the maximum number of the value decrease over all increasing chains of tuples of variable values for at least one function from system \(F\); \(u\) is the maximum (over all non-monotone basis functions and all increasing chains of tuples of variable values) length of subsequence such that the values of the function decrease over these subsequences.
MSC:
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
Keywords:
combinational machine (logic circuits); circuits complexity; bases with zero weight elements; \(k\)-valued logic functions; inversion complexity; Markov’s theorem; Shannon functionReferences:
| [1] | A. A. Markov, {\it On the inversion complexity of systems of functions}, Doklady Academii Nauk SSSR, 116:6 (1957), 917-919 (in Russian). English translation in: {\it J. of ACM}, 5:4 (1958), 331-334. MR0097303 · Zbl 0079.24601 |
| [2] | A. A. Markov, {\it On the inversion complexity of systems of Boolean functions}, Doklady Academii Nauk SSSR, 150:3 (1963), 477-479 (in Russian). English translation in: {\it Soviet} {\it Math. Doklady}, 4 (1963), 694-696. MR0151384 · Zbl 0171.27903 |
| [3] | V. V. Kochergin and A. V. Mikhailovich, {\it Inversion complexity of functions of multi-valued} {\it logic}, Cornell University Library, arXiv.org > cs > arXiv:1510.05942 (2015). |
| [4] | V. V. Kochergin and A. V. Mikhailovich, {\it The minimum number of negations in circuits for} {\it systems of multi-valued logic functions}, Diskretnaya Matematika, 28:4 (2016), 80-90 (in Russian). English translation in: {\it Discrete Math. Appl.}. 27(5) (2017), 295-302. MR3699323 · Zbl 1441.94117 |
| [5] | O. B. Lupanov, {\it Asymptotic Estimations of Complexity of Control Systems}, Moscow: Mosc. State Univ. Press, 1984 (in Russian). |
| [6] | J. E. Savage, {\it The complexity of computing}, New York: Wiley, 1976. MR0495205 · Zbl 0391.68025 |
| [7] | E. N. Gilbert, {\it Lattice theoretic properties of frontal switching functions}, J. Math. Phys., 33 (1954), 56-67. MR0062650 · Zbl 0055.20109 |
| [8] | E. I. Nechiporuk, {\it On the complexity of circuits in some bases containing nontrivial elements} {\it with zero weights}, Problemy Kibernetiki, 8 (1962), 123-160 (in Russian). MR0168422 · Zbl 0201.48701 |
| [9] | M. J. Fischer, {\it The complexity of negation-limited networks — a brief survey}, Springer Lect. Notes in Comput. Sci., 33 (1975), 71-82. MR0400784 · Zbl 0327.68055 |
| [10] | M. J. Fischer, {\it Lectures on network complexity}, Technical Report 1104, CS Department, Yale University, (1974, revised 1996). |
| [11] | K. Tanaka and T. Nishino, {\it On the complexity of negation-limited Boolean networks}, Proceedings of the 26th annual ACM symposium on theory of computing, STOC ’94, (1994), 38-47. Zbl 1345.68166 · Zbl 1345.68166 |
| [12] | K. Tanaka, T. Nishino, and R. Beals, {\it Negation-limited circuit complexity of symmetric} {\it functions}, Inf. Proc. Lett., 59:5 (1996), 273-279. MR1417643 · Zbl 0875.68431 |
| [13] | S. Sung and K. Tanaka, {\it Limiting negations in bounded-depth circuits: an extension of} {\it Markov’s theorem}, Lect. Notes in Comput. Sci., 2906 (2003), 108-116. MR2087551 · Zbl 1205.68176 |
| [14] | H. Morizumi, {\it A note on the inversion complexity of Boolean functions in Boolean formulas}, Cornell University Library, arXiv.org > cs > arXiv:0811.0699 (2008). |
| [15] | Jukna S., {\it Boolean Function Complexity. Advances and Frontiers, }Berlin-Heidelberg: Springer, 2012. MR2895965 · Zbl 1235.94005 |
| [16] | E. Blais, C. L. Canonne, I. C. Oliveira, R. A. Servedio and L.-Y. Tan, {\it Learning circuits with} {\it few negations}, Electronic Colloquium on Computational Complexity, Report No. 144 (2014). · Zbl 1375.68063 |
| [17] | S. Guo, T. Malkin, I. C. Oliveira and A. Rosen, {\it The power of negations in cryptography}, Lect. Notes in Comput. Sci., 9014 (2015), 36-65. MR3346221 ON NON-MONOTONE COMPLEXITY OF MULTI-VALUED LOGIC FUNCTIONS1107 · Zbl 1354.94032 |
| [18] | V. V. Kochergin and A. V. Mikhailovich, {\it Some extensions of inversion complexity of Boolean} {\it functions}, Cornell University Library, arXiv.org > cs > arXiv:1506.04485 (2015). |
| [19] | V. V. Kochergin and A. V. Mikhailovich, {\it On the complexity of circuits in bases containing} {\it monotone elements with zero weights}, Prikladnaya Diskretnaya Matematika, 30 · Zbl 1527.94098 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
