Том 25, номер 3, 2018 г., Стр. 36-94

УДК 519.714
Рычков К. Л.
О сложности реализации линейной булевой функции в классе $\pi$-схем

Аннотация:
Для сложности в классе $\pi$-схем линейной булевой функции, существенно зависящей от $6$ переменных, на основе метода В. М. Храпченко получена точная нижняя оценка $40$. Дано упрощённое доказательство ряда нижних оценок сложности линейных булевых функций, полученных ранее на базе того же метода.
Библиогр. 18.

Ключевые слова: булева функция, $\pi$-схема, нижняя оценка сложности.

DOI: 10.17377/daio.2018.25.589

Рычков Константин Леонидович ¹
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: rychkov@math.nsc.ru

Статья поступила 18 сентября 2017 г.
Исправленный вариант — 10 мая 2018 г.

Литература

[1] Августинович С. В., Васильев Ю. Л., Рычков К. Л. Формульная сложность тернарной линейной функции // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 3. С. 3–12.

[2] Васильев Ю. Л., Рычков К. Л. Нижняя оценка формульной сложности тернарной линейной функции // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 4. С. 15–26.

[3] Рычков К. Л. Модификация метода В. М. Храпченко и применение её к оценкам сложности $\Pi$-схем для кодовых функций // Дискрет. анализ. Вып. 42. 1985. С. 91–98.

[4] Рычков К. Л. О нижних оценках сложности параллельно-последовательных контактных схем, реализующих линейные булевы функции // Сиб. журн. исслед. операций. 1994. Т. 1, № 4. С. 33–52.

[5] Рычков К. Л. О нижних оценках формульной сложности линейной булевой функции // Сиб. электрон. мат. изв. 2014. Т. 11. С. 165–184.

[6] Рычков К. Л. Достаточные условия локальной бесповторности минимальных $\pi$-схем, реализующих линейные булевы функции // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 5. С. 71–85.

[7] Субботовская Б. А. О реализации линейных функций формулами в базисе $\lor$, $\&$, $^-$ // Докл. АН СССР. 1961. Т. 136, № 3. С. 553–555.

[8] Храпченко В. М. О сложности реализации линейной функции в классе $\Pi$-схем // Мат. заметки. 1971. Т. 9, № 1. С. 35–40.

[9] Храпченко В. М. Об одном методе получения нижних оценок сложности $\Pi$-схем // Мат. заметки. 1971. Т. 10, № 1. С. 83–92.

[10] Черухин Д. Ю. К вопросу о логическом представлении счётчика чётности // Неформальная наука. 2009. № 2. С. 14–23.

[11] Яблонский С. В. Реализация линейной функции в классе $\Pi$-схем // Докл. АН СССР. 1954. Т. 94, № 5. С. 805–806.

[12] Harary F. Graph theory. Reading, MA: Addison-Wesley, 1969. 273 p.

[13] Håstad J. The shrinkage exponent of de Morgan formulae is 2 // SIAM J. Comput. 1998. Vol. 27, No. 1. P. 48–64.

[14] Karchmer M., Wigderson A. Monotone circuits for connectivity require super-logarithmics depth // SIAM J. Discrete Math. 1990. Vol. 3, No. 2. P. 255–265.

[15] Lee T. A new rank technique for formula size lower bounds // Proc. 24th Annu. Symp. Theoretical Aspects of Computer Science (Aachen, Germany, Feb. 22–24, 2007). Heidelberg: Springer-Verl., 2007. P. 145–156. (Lect. Notes Comput. Sci.; Vol. 4393).

[16] Razborov A. Applications of matrix methods to the theory of lower bounds in computational complexity // Combinatorica. 1990. Vol. 10, No. 1. P. 81–93.

[17] Turán P. Eine Extremalaufgabe aus der Graphentheorie // Mat. Fiz. Lapok. 1941. Vol. 48, No. 1. P. 436–452.

[18] Wegener I. The complexity of Boolean functions. Chichester, UK: Wiley, 1987.