Ю. Л. Васильев, К. Л. Рычков, “Нижняя оценка формульной сложности тернарной линейной функции”, Дискретн. анализ и исслед. опер., 2013, том 20, выпуск 4,страницы 15

Эта публикация цитируется в 4 статьях

Нижняя оценка формульной сложности тернарной линейной функции

Ю. Л. Васильев, К. Л. Рычков

Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

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

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

УДК: 519.714

Статья поступила: 18.03.2013