Том 22, номер 5, 2015 г., Стр. 71–85

УДК 519.714
Рычков К. Л.
Достаточные условия локальной бесповторности минимальных π-схем, реализующих линейные булевы функции

Аннотация:
Сформулированы достаточные условия локальной бесповторности минимальных π-схем, реализующих линейные булевы функции. Выполнение этих условий приводит к описанию классов минимальных π-схем, реализующих линейные булевы функции, существенно зависящие от n переменных.
Ил. 2, библиогр. 12.

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

DOI: 10.17377/daio.2015.22.481

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

Статья поступила 16 марта 2015 г.
Исправленный вариант — 23 июля 2015 г.

Литература

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

[2] Рычков К. Л. О минимальных π-схемах для линейных булевых функций // Дискрет. анализ. Вып. 51. 1991. С. 84–104.

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

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

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

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

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

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

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

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

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

[12] Wegener I. The complexity of Boolean functions. Chichester: Wiley, 1987. 458 p.