Bounds of non-monotone complexity for the multi-valued logic functions
The non-monotone complexity of realization of k-valued logic functions by circuits in a special basis was investigated. The basis consists of elements of two types: the first type comprises all monotone functions (with respect to the order 0 < 1 < 2 <···< k−1 ) with zero weight; the seco...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kazan Federal University
2020-09-01
|
| Series: | Учёные записки Казанского университета: Серия Физико-математические науки |
| Subjects: | |
| Online Access: | https://kpfu.ru/uz-eng-phm-2020-3-6.html |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849220842129457152 |
|---|---|
| author | V.V. Kochergin A.V. Mikhailovich |
| author_facet | V.V. Kochergin A.V. Mikhailovich |
| author_sort | V.V. Kochergin |
| collection | DOAJ |
| description | The non-monotone complexity of realization of k-valued logic functions by circuits in a special basis was investigated. The basis consists of elements of two types: the first type comprises all monotone functions (with respect to the order 0 < 1 < 2 <···< k−1 ) with zero weight; the second type includes non-monotone elements with unit weight, the non-empty set of which is finite. The upper and lower bounds of non-monotone complexity (the minimum number of non-monotone elements) for an arbitrary k-valued logic function were established. The difference between the upper and lower bounds does not exceed a universal constant. The difference between the best upper and lower bounds known before is a constant that depends on the basis. The range of values for these constants is infinite. |
| format | Article |
| id | doaj-art-89b237d69a4849869e4ec0443c9f89d3 |
| institution | Kabale University |
| issn | 2541-7746 2500-2198 |
| language | English |
| publishDate | 2020-09-01 |
| publisher | Kazan Federal University |
| record_format | Article |
| series | Учёные записки Казанского университета: Серия Физико-математические науки |
| spelling | doaj-art-89b237d69a4849869e4ec0443c9f89d32024-12-02T08:48:27ZengKazan Federal UniversityУчёные записки Казанского университета: Серия Физико-математические науки2541-77462500-21982020-09-01162331132110.26907/2541-7746.2020.3.311-321Bounds of non-monotone complexity for the multi-valued logic functionsV.V. Kochergin0A.V. Mikhailovich1Lomonosov Moscow State University, Moscow, 119991 Russia; National Research University – Higher School of Economics, Moscow, 101000 Russia National Research University – Higher School of Economics, Moscow, 101000 RussiaThe non-monotone complexity of realization of k-valued logic functions by circuits in a special basis was investigated. The basis consists of elements of two types: the first type comprises all monotone functions (with respect to the order 0 < 1 < 2 <···< k−1 ) with zero weight; the second type includes non-monotone elements with unit weight, the non-empty set of which is finite. The upper and lower bounds of non-monotone complexity (the minimum number of non-monotone elements) for an arbitrary k-valued logic function were established. The difference between the upper and lower bounds does not exceed a universal constant. The difference between the best upper and lower bounds known before is a constant that depends on the basis. The range of values for these constants is infinite.https://kpfu.ru/uz-eng-phm-2020-3-6.htmllogic circuitscircuit complexityk-valued logic functionsbases with zero weight elementsinversion complexitynon-monotone complexity |
| spellingShingle | V.V. Kochergin A.V. Mikhailovich Bounds of non-monotone complexity for the multi-valued logic functions Учёные записки Казанского университета: Серия Физико-математические науки logic circuits circuit complexity k-valued logic functions bases with zero weight elements inversion complexity non-monotone complexity |
| title | Bounds of non-monotone complexity for the multi-valued logic functions |
| title_full | Bounds of non-monotone complexity for the multi-valued logic functions |
| title_fullStr | Bounds of non-monotone complexity for the multi-valued logic functions |
| title_full_unstemmed | Bounds of non-monotone complexity for the multi-valued logic functions |
| title_short | Bounds of non-monotone complexity for the multi-valued logic functions |
| title_sort | bounds of non monotone complexity for the multi valued logic functions |
| topic | logic circuits circuit complexity k-valued logic functions bases with zero weight elements inversion complexity non-monotone complexity |
| url | https://kpfu.ru/uz-eng-phm-2020-3-6.html |
| work_keys_str_mv | AT vvkochergin boundsofnonmonotonecomplexityforthemultivaluedlogicfunctions AT avmikhailovich boundsofnonmonotonecomplexityforthemultivaluedlogicfunctions |