Том 26, номер 4, 2019 г., Стр. 74-107

УДК 519.714
Рычков К. Л.
О совершенности минимальных правильных разбиений множества ребер $n$-мерного куба

Аннотация:
Доказано, что при $n = 3, 5$ и при $n$, равном степени двойки, любое минимальное правильное разбиение множества рёбер $n$-мерного куба является совершенным. Следствием этих результатов является описание классов всех минимальных параллельно-последовательных контактных схем ($\pi$-схем), реализующих линейные булевы функции, существенно зависящие от $n$ переменных при соответствующих значениях $n$.
Библиогр. 16.

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

DOI: 10.33048/daio.2019.26.662

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

Статья поступила 10 июня 2019 г.
После доработки — 29 июля 2019 г.
Принята к публикации 28 августа 2019 г.

Литература

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

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

[3] Храпченко В. М. Упрощённое доказательство одной нижней оценки сложности // Дискрет. математика. 2013. Т. 25, № 2. С. 82–84.

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

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

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

[7] Håstad J. The shrinkage exponent is 2 // SIAM J. Comput. 1998. Vol. 27. P. 48–64.

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

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

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

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

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

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

[14] Рычков К. Л. О сложности реализации линейной булевой функции в классе $\pi$-схем // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 3. С. 36–94.

[15] Harary F. Graph theory. London: Addison-Wesley, 1969. 273 p.

[16] Turán P. Eine Extremalaufgabe aus der Graphentheorie // Mat. Fiz. Lapok. 1941. Bd 48. S. 436–452. [Hungarian].