|
|
Дискретн. анализ и исслед. опер., 2011, том 18, номер 5, страницы 38–53
(Mi da664)
|
 |
|
 |
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Редкие циркулянтные матрицы и нижние оценки сложности некоторых булевых операторов
М. И. Гринчук, И. С. Сергеев
Московский гос. университет им. М. В. Ломоносова, Москва, Россия
Аннотация:
Доказана нижняя оценка $\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.
Ключевые слова:
сложность, циркулянтная матрица, редкая матрица, проблема Заранкевича, монотонная схема, вентильная схема, булева сумма, булева свёртка.
 Полный текст:
PDF файл (308 kB)
Список литературы:
PDF файл
HTML файл
Реферативные базы данных:
 
Тип публикации:
Статья
УДК:
519.7
Статья поступила: 27.01.2011
Образец цитирования:
М. И. Гринчук, И. С. Сергеев, “Редкие циркулянтные матрицы и нижние оценки сложности некоторых булевых операторов”, Дискретн. анализ и исслед. опер., 18:5 (2011), 38–53
Цитирование в формате AMSBIB
\RBibitem{GriSer11}
\by М.~И.~Гринчук, И.~С.~Сергеев
\paper Редкие циркулянтные матрицы и нижние оценки сложности некоторых булевых операторов
\jour Дискретн. анализ и исслед. опер.
\yr 2011
\vol 18
\issue 5
\pages 38--53
\mathnet{http://mi.mathnet.ru/da664}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2918328}
\zmath{https://zbmath.org/?q=an:1249.68087}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da664 http://mi.mathnet.ru/rus/da/v18/i5/p38
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
С. Б. Гашков, И. С. Сергеев, “Об одном методе получения нижних оценок сложности монотонных арифметических схем, вычисляющих действительные многочлены”, Матем. сб., 203:10 (2012), 33–70
   ; S. B. Gashkov, I. S. Sergeev, “A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials”, Sb. Math., 203:10 (2012), 1411–1447  -
Boyar J., Find M.G., “Cancellation-Free Circuits in Unbounded and Bounded Depth”, Theor. Comput. Sci., 590 (2015), 17–26
 -
M. Find, M. Goos, M. Jarvisalo, P. Kaski, M. Koivisto, J. H. Korhonen, “Separating or, sum, and xor circuits”, J. Comput. Syst. Sci., 82:5 (2016), 793–801
|
| Просмотров: |
| Эта страница: | 352 | | Полный текст: | 78 | | Литература: | 28 | | Первая стр.: | 8 |
|
Пользовательское соглашение