RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ЛОМИ, 1976, том 60, страницы 38–48 (Mi znsl2068)

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

Использование понятий отделенности и независимости для получения нижних оценок сложности схем

Д. Ю. Григорьев


Аннотация: Заметка состоит из двух независимых частей, в первой части введено понятие $(m,c)$-системы для набора линейных форм и подучена нижняя оценка для алгебраической сложности вычисления $(m,c)$-систем на алгебраических схемах специального вида. Во второй части введено понятие $l$-независимости набора булевских функций и получена нижняя оценка для некоторой меры сложности схем из булевских функций для схем, вычисляющих $l$-независимый набор, в качестве следствия показано, что обычный алгорифм умножения матриц или полиномов можно реализовать на схеме из булевских функций так, что эта реализация будет оптимальна относительно выбранной меры сложности. Библ. 5 назв.

УДК: 518.5, 519.1


 Англоязычная версия: Journal of Soviet Mathematics, 1980, 14:5, 1450–1457

Реферативные базы данных:


© МИАН, 2024