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

Зап. научн. сем. ЛОМИ, 1982, том 118, страницы 25–82 (Mi znsl3977)

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

Нижние оценки в алгебраической сложности вычислений

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


Аннотация: Настоящая работа представляет собой обзор по избранным методам в получении нижних оценок в алгебраической сложности, приведем оглавление.
Введение. I. Основные понятия. Глава I. Алгебро-геометрический подход к получению нижних оценок сложности вычисления многочленов. 2. Вычисление многочлена с “общими” коэффициентами. 3. Сложность вычисления индивидуальных многочленов. 4. Метод, степени и его обобщения (случай бесконечного основного поля). 5. Метод степени (случай конечного основного поля). 6. Аддитивная сложность и вещественные корни. Глава II. Нижние оценки мультипликативной сложности в задачах линейной алгебры. 7. Мультипликативная сложность и ранг. 8. Ранг пары билинейных форм. 9. Мультипликативная сложность билинейной формы над коммутативным кольцом. 10. Оценки ранга алгебр. 11. Линеаризованная мультипликативная сложность. Глава III. Сложность в неветвящихся программах нестандартных типов. 12. Иррациональная сложность вычисления алгебраических функций. 13. Монотонные вычисления. 14. Нижние оценки для произведения времени и памяти. 15. Методы теории графов в алгебраической сложности. 16. Аддитивная сложность в треугольных и направленных вычислениях и разложение Брюа.

УДК: 519.5



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


© МИАН, 2024