Том 25, номер 1, 2018 г., Стр. 42–74

УДК 519.714
Кочергин В. В., Михайлович А. В.
О сложности функций многозначной логики в одном бесконечном базисе

Аннотация:
Исследуется сложность реализации функций $k$-значной логики $(k \ge 3)$ схемами из функциональных элементов в бесконечном базисе, состоящем из отрицания Поста, т. е. функции $x + 1$ (mod $k$), и всех монотонных функций. Под сложностью понимается общее число элементов в схеме. Для произвольной функции $f$ установлены отличающиеся друг от друга не более чем на единицу нижняя и верхняя оценки сложности вида $3$log$_3$ $(d(f)+ 1)+O(1)$, где $d(f)$ — максимальное (максимум берётся по всем возрастающим цепям наборов значений переменных) число изменений значений функции $f$ с большего значения на меньшее. Найдено точное значение соответствующей функции Шеннона, характеризующей сложность реализации самой сложно реализуемой функции от заданного числа переменных.
Ил. 4, библиогр. 24.

Ключевые слова: функции многозначной логики, логическая схема, бесконечный базис, инверсионная сложность.

DOI: 10.17377/daio.2018.25.587

Кочергин Вадим Васильевич ¹
Михайлович Анна Витальевна ²
1. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 1, 119991 Москва, Россия
2. Национальный исследовательский университет «Высшая школа экономики»,
ул. Мясницкая, 20, 101000 Москва, Россия
е-mail: vvkoch@yandex.ru, avmikhailovich@gmail.com

Статья поступила 4 августа 2017 г.
Исправленный вариант — 6 октября 2017 г.

Литература

[1] Карпова Н. А. О некоторых свойствах функций Шеннона // Мат. заметки. 1970. Т. 8, вып. 5. С. 663–674.

[2] Касим-Заде О. М. О сложности схем в одном бесконечном базисе // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 1994. № 6. С. 40–44.

[3] Касим-Заде О. М. О порядках роста функций Шеннона сложности схем над бесконечными базисами // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 2013. № 3. С. 55–57.

[4] Кочергин В. В. Теория вентильных схем (современное состояние) // Дискретная математика и её приложения. Вып. 7. М.: Изд-во ИПМ РАН, 2013. С. 23–40.

[5] Кочергин В. В., Михайлович А. В. О сложности схем в базисах, содержащих монотонные элементы с нулевыми весами // Прикл. дискрет. математика. 2015. № 4. С. 24–31.

[6] Кочергин В. В., Михайлович А. В. О минимальном числе отрицаний при реализации систем функций $k$-значной логики // Дискрет. математика. 2016. Т. 28, вып. 4. С. 80–90.

[7] Лупанов О. Б. О синтезе схем из пороговых элементов // Пробл. кибернетики. Вып. 26. М.: Наука, 1973. C. 109–140.

[8] Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во Моск. ун-та, 1984.

[9] Марков А. А. Об инверсионной сложности систем функций // Докл. АН СССР. 1957. Т. 116, № 6. С. 917–919.

[10] Марков А. А. Об инверсионной сложности систем булевых функций // Докл. АН СССР. 1963. Т. 150, № 3. С. 477–479.

[11] Нечипорук Э. И. О сложности схем в некоторых базисах, содержащих нетривиальные элементы с нулевыми весами // Пробл. кибернетики. Вып. 8. М.: Физматгиз, 1962. C. 123–160.

[12] Нечипорук Э. И. О синтезе схем из пороговых элементов // Пробл. кибернетики. Вып. 11. М.: Наука, 1964. С. 49–62.

[13] Подольская О. В. Сложность реализации симметрических булевых функций схемами в базисе антицепных функций // Дискрет. математика. 2015. Т. 27, вып. 3. С. 95–107.

[14] Сэвидж Д. Е. Сложность вычислений. М.: Факториал, 1998.

[15] Blais E., Canonne C. L., Oliveira I. C., Servedio R. A., Tan L.-Y. Learning circuits with few negations // Electron. Colloq. Comput. Complex. Rep. No. 144. 2014.

[16] Gilbert E. N. Lattice theoretic properties of frontal switching functions // J. Math. Phys. 1954. V. 33, No. 1. P. 57– 67.

[17] Guo S., Malkin T., Oliveira I. C., Rosen A. The power of negations in cryptography // Theory of cryptography. Heidelberg: Springer-Verl., 2015. P. 36–65. (Lect. Notes Comput. Sci.; Vol. 9014).

[18] Fischer M. J. The complexity of negation-limited networks — A brief survey // Automata theory and formal languages. Berlin: Springer-Verl., 1975. P. 71–82. (Lect. Notes Comput. Sci.; Vol. 33).

[19] Jukna S. Boolean function complexity: Advances and frontiers. Heidelberg: Springer-Verl., 2012. (Algorithms Comb.; Vol. 27).

[20] Kochergin V. V., Mikhailovich A. V. Some extensions of the inversion complexity of Boolean functions. 2015. (Cornell Univ. Libr. e-Print Archive; arXiv:1506.04485).

[21] Kochergin V. V., Mikhailovich A. V. Inversion complexity of functions of multi-valued logic. 2015. (Cornell Univ. Libr. e-Print Archive; arXiv: 1510.05942).

[22] Morizumi H. A note on the inversion complexity of Boolean functions in Boolean formulas. 2008. (Cornell Univ. Libr. e-Print Archive; arXiv: 0811.0699).

[23] Pippenger N. The mimimum number of edges in graphs with prescribed paths // Math. Syst. Theory. 1979. V. 12, No. 4. P. 325–346.

[24] Sung S., Tanaka K. Limiting negations in bounded-depth circuits: An extension of Markovs theorem // Algorithms and computation. Heidelberg: Springer-Verl., 2003. P. 108–116. (Lect. Notes Comput. Sci.; Vol. 2906).