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