Оценки немонотонной сложности функций многозначной логики

В.В. Кочергин^1,2 , А.В. Михайлович²

¹Московский государственный университет имени М.В. Ломоносова, г. Москва, 119991, Россия

²Национальный исследовательский университет «Высшая школа экономики», г. Москва, 101000, Россия

Полный текст PDF
DOI: 10.26907/2541-7746.2020.3.311-321

Для цитирования: Кочергин В.В., Михайлович А.В. Оценки немонотонной сложности функций многозначной логики // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2020. – Т. 162, кн. 3. – С. 311–321. – doi: 10.26907/2541-7746.2020.3.311-321.

For citation: Kochergin V.V., Mikhailovich A.V. Bounds of non-monotone complexity for the multi-valued logic functions. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 311–321. doi: 10.26907/2541-7746.2020.3.311-321. (In Russian)

Аннотация

Исследована задача о сложности реализации функций многозначной логики логическими схемами в базисе, состоящем из элементов двух типов. Элементами первого типа являются произвольные монотонные (относительно стандартного порядка) функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго типа, каждой такой функции приписан единичный вес. Установлены верхняя и нижняя оценки немонотонной сложности (минимального достаточного для реализации числа немонотонных элементов в схеме) произвольной функции k-значной логики, разность между которыми не превосходит некоторой абсолютной константы. Разность наилучших известных до этого верхней и нижней оценок отличалась на константу, зависящую от базиса, при этом множество значений таких констант неограничено.

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

Благодарности. Работа первого автора выполнена при частичной финансовой поддержке РФФИ (проект № 18-01-00337).

Литература

1. Марков А.А. Об инверсионной сложности систем функций // Докл. АН СССР. – 1957. – Т. 116, № 6. – С. 917–919.
2. Марков А.А. Об инверсионной сложности систем булевых функций // Докл. АН СССР. – 1963. – Т. 150, № 3. – С. 477–479.
3. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. – М.: Изд-во Моск. ун-та, 1984. – 137 с.
4. Savage J.E. The Complexity of Computing. – N. Y.: Wiley, 1976. – 391 p.
5. Кочергин В.В., Михайлович А.В. О сложности схем в базисах, содержащих монотонные элементы с нулевыми весами // Прикл. дискрет. матем. – 2015. – № 4. – С. 25–32. – doi: 10.17223/20710410/30/2.
6. Кочергин В.В., Михайлович А.В. О минимальном числе отрицаний при реализации систем функций k -значной логики // Дискрет. матем. – 2016. – Т. 28, Вып. 4. – С. 80–90. – doi: 10.4213/dm1394.
7. Кочергин В.В., Михайлович А.В. О сложности функций многозначной логики в одном бесконечном базисе // Дискрет. анализ и исслед. операций. – 2018. – Т. 25, № 1. – С. 42–74. – doi: 10.17377/daio.2018.25.587.
8. Кочергин В.В., Михайлович А.В. О схемной сложности функций k -значной логики в одном бесконечном базисе // Прикл. матем. и информатика. – 2018. – № 58. – С. 21–34.
9. Kochergin V.V., Mikhailovich A.V. Asymptotics of growth for non-monotone complexity of multi-valued logic function systems // Sib. Electron. Math. Rep. – 2017. – V. 14. – P. 1100–1107. – doi: 10.17377/semi.2017.14.093.
10. Кочергин В.В., Михайлович А.В. Точное значение немонотонной сложности булевых функций // Матем. заметки. – 2019. – Т. 105, Вып. 1. – С. 32–41. – doi: 10.4213/mzm11693.

Поступила в редакцию 17.08.2020

Кочергин Вадим Васильевич, доктор физико-математических наук, профессор кафедры дискретной математики; профессор кафедры высшей математики

Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия

Национальный исследовательский университет «Высшая школа экономики» ул. Мясницкая, д. 20, г. Москва, 101000, Россия

E-mail: vvkoch@yandex.ru

Михайлович Анна Витальевна, кандидат физико-математических наук, доцент кафедры высшей математики

Национальный исследовательский университет «Высшая школа экономики» ул. Мясницкая, д. 20, г. Москва, 101000, Россия

E-mail: avmikhailovich@gmail.com

Контент доступен под лицензией Creative Commons Attribution 4.0 License.