Аннотация:
Заметка состоит из двух независимых частей, в первой части
введено понятие (m,c)-системы для набора линейных форм и подучена
нижняя оценка для алгебраической сложности вычисления (m,c)-систем на алгебраических схемах специального вида. Во второй части
введено понятие l-независимости набора булевских функций и получена нижняя оценка для некоторой меры сложности схем из булевских
функций для схем, вычисляющих l-независимый набор, в качестве
следствия показано, что обычный алгорифм умножения матриц
или полиномов можно реализовать на схеме из булевских функций
так, что эта реализация будет оптимальна относительно выбранной
меры сложности. Библ. 5 назв.
Образец цитирования:
Д. Ю. Григорьев, “Использование понятий отделенности и независимости
для получения нижних оценок сложности схем”, Исследования по конструктивной математике и математической логике. VII, Зап. научн. сем. ЛОМИ, 60, Изд-во «Наука», Ленинград. отд., Л., 1976, 38–48; J. Soviet Math., 14:5 (1980), 1450–1457
\RBibitem{Gri76}
\by Д.~Ю.~Григорьев
\paper Использование понятий отделенности и~независимости
для получения нижних оценок сложности схем
\inbook Исследования по конструктивной математике и математической логике.~VII
\serial Зап. научн. сем. ЛОМИ
\yr 1976
\vol 60
\pages 38--48
\publ Изд-во «Наука», Ленинград. отд.
\publaddr Л.
\mathnet{http://mi.mathnet.ru/znsl2068}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=660685}
\zmath{https://zbmath.org/?q=an:0449.94030|0341.94020}
\transl
\jour J. Soviet Math.
\yr 1980
\vol 14
\issue 5
\pages 1450--1457
\crossref{https://doi.org/10.1007/BF01693976}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl2068
https://www.mathnet.ru/rus/znsl/v60/p38
Эта публикация цитируется в следующих 11 статьяx:
Б. В. Коноплев, “Об обращении функции Валианта ранговой устойчивости матрицы”, Материалы 20 Международной Саратовской зимней школы «Современные проблемы теории функций и их приложения», Саратов, 28 января — 1 февраля 2020 г. Часть 1, Итоги науки и техн. Соврем. мат. и ее прил. Темат. обз., 199, ВИНИТИ РАН, М., 2021, 60–65
Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, “Parameterized low-rank binary matrix approximation”, Data Min Knowl Disc, 34:2 (2020), 478
Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, Meirav Zehavi, “Matrix Rigidity from the Viewpoint of Parameterized Complexity”, SIAM J. Discrete Math., 32:2 (2018), 966
S. A. Vakulenko, D. Yu. Grigor'ev, “Эволюция в случайном окружении и структурная неустойчивость”, Зап. научн. сем. ПОМИ, 325 (2005), 28–60; S. A. Vakulenko, D. Yu. Grigor'ev, “Evolution in random environment and structural instability”, J. Math. Sci. (N. Y.), 138:3 (2006), 5644–5662
Б. С. Кашин, А. А. Разборов, “Новые нижние оценки устойчивости матриц Адамара”, Матем. заметки, 63:4 (1998), 535–540; B. S. Kashin, A. A. Razborov, “Improved lower bounds on the rigidity of Hadamard matrices”, Math. Notes, 63:4 (1998), 471–475
K. Abrahamson, Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, 1990, 412
Karl Abrahamson, 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), 1986, 402
D. Yu. Grigor'ev, “Lower bounds in algebraic computational complexity”, J Math Sci, 29:4 (1985), 1388
Zvi M. Kedem, 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), 1982, 379
А. О. Слисенко, “Сложностные задачи теории вычислений”, УМН, 36:6(222) (1981), 21–103; A. O. Slisenko, “Complexity problems in computational theory”, Russian Math. Surveys, 36:6 (1981), 23–125
Цитирование в формате AMSBIB
Обратная связь: