Том 20, номер 4, 2013 г., Стр. 15-26

УДК 519.714
Васильев Ю. Л., Рычков К. Л.
Нижняя оценка формульной сложности тернарной линейной функции

Аннотация:
Установлено, что формульная сложность тернарной линейной функции, зависящей от $n$ переменных, не меньше $n^2+\frac32n-o(n)$.
Библиогр. 8.

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

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

Статья поступила 18 марта 2013 г.

Литература

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

[2] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике - М.: Физматлит, 2005. - 416 с.

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

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

[5] Рычков К. Л. О сложности обобщённых контактных схем // Дискрет. анализ и исслед. операций. - 2009. - Т. 16, № 5. - С. 78–87.

[6] Рычков К. Л. Нижняя оценка сложности реализации в классе –схем q-ичного счётчика кратности q // Дискрет. анализ и исслед. операций. - 2010. - Т. 17, № 6. - С. 68–76.

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

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