Том 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 г.
Литература
[1] Гашков С. Б., Сергеев И. С. О сложности линейных булевых операторов с редкими матрицами // Дискрет. анализ и исслед. операций. — 2010. — Т. 17, № 3. — C. 3–18.
[2] Гринчук М. И. О сложности реализации циклических булевых матриц вентильными схемами // Изв. вузов. Математика. — 1988. — T. 7. — C. 39–44.
[3] Коршунов А. Д. Монотонные булевы функции // Успехи мат. наук. — 2003. — Т. 58, вып. 5. — C. 89–162.
[4] Лупанов О. Б. О вентильных и контактно-вентильных схемах // Докл. АН СССР. — 1956. — Т. 111, № 6. — С. 1171–1174.
[5] Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — М.: Изд-во МГУ, 1984. — 138 с.
[6] Мельхорн К. Некоторые замечания, касающиеся булевых сумм // Кибернетический сборник. Вып. 18. — М.: Мир, 1981. — C. 39–45.
[7] Эрдеш П., Спенсер Дж. Вероятностные методы в комбинаторике. — М.: Мир, 1976. — 130 с.
[8] Blum N. On negations in Boolean networks. — Berlin; Heidelberg: Springer-Verl., 2009. — P. 18–29. (Lect. Notes Comput. Sci.; Vol. 5760.)
[9] Gardner R. J., Gronchi P. A Brunn–Minkowski inequality for the integer lattice // Trans. Amer. Math. Soc. — 2001. — Vol. 353, N 10. — P. 3995–4024.
[10] Ruzsa I. Z. Sum of sets in several dimensions // Combinatorica. — 1994. — Vol. 14. — P. 485–490.
[11] Wegener I. The complexity of boolean functions. — Stuttgart: Wiley, 1987. — 470 p.
