EN|RU

Том 18, номер 5, 2011 г., Стр. 38-53

УДК 519.7
Гринчук М. И., Сергеев И. С.
Редкие циркулянтные матрицы и нижние оценки сложности некоторых булевых операторов

Аннотация:
Доказана нижняя оценка $\Omega(\frac{k+l}{k^2l^2}N^{2-\frac{k+l+2}{kl}})$ максимально возможного веса $(k,l)$-редкой (т.е. не содержащей единичных подматриц размера $k\times l$) циркулянтной матрицы порядка $N$. Эта оценка близка к известной оценке для класса всех $(k,l)$-редких матриц. В качестве следствия получены новые нижние оценки для нескольких мер сложности систем булевых сумм и нижняя оценка $\Omega(N^2\log^{-6}N)$ монотонной сложности булевой свёртки порядка $N$.
Ил. 1, библиогр. 11.

Ключевые слова: сложность, циркулянтная матрица, редкая матрица, проблема Заранкевича, монотонная схема, вентильная схема, булева сумма, булева свёртка.

Гринчук Михаил Иванович 1
Сергеев Игорь Сергеевич 1

1. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 119991 Москва, Россия
е-mail: grinchuk@nw.math.msu.su, isserg@gmail.com

Статья поступила 27 января 2011 г.

 © Институт математики им. С. Л. Соболева, 2015