Разборов А.А. Алгебраическая сложность

Электронное издание. — М.: МЦНМО, 2016. — 31 с. — ISBN: 978-5-4439-3032-9.Брошюра написана по материалам курса, прочитанного автором в 2010 г. в Летней школе «Современная математика». В ней рассказывается об основных понятиях теории алгебраической сложности и приводятся её начальные утверждения. Рассматриваются задачи эффективного вычисления полиномов и билинейных форм, матричного умножения и алгебраической теории NP-полноты.
Книга представляет интерес для широкого круга сравнительно подготовленных читателей, интересующихся математикой.Теория алгебраической сложности была создана во многом благодаря усилиям немецкого математика Фолькера Штрассена, кото-
рому принадлежат многие классические теоремы в этой области; ее название связано с тем, что она оперирует с полиномами. В алгебраической сложности, как и во многих других разделах теории сложности, имеется много важных задач, которые очень просто формулируются, но остаются открытыми уже в течение десятилетий. Ниже речь пойдет о классических результатах этой области, которым приблизительно 30-40 лет.Вычисление полиномов от одной переменной.
Полиномы от многих переменных.
Перемножение полиномов и вычисление билинейных форм.
Умножение матриц.
Перманент и VNP-полнота.
Приложение. Необходимые сведения.
Список литературы.