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

Как грамотно вычислить значение полинома от многих переменных? Можно, конечно, посчитать по отдельности каждый входящий в него моном и результаты сложить, но нельзя ли придумать способ сэкономить на числе используемых операций хотя бы для некоторых наиболее важных и часто встречающихся полиномов?

Изучением таких вопросов как раз и занимается теория алгебраической сложности вычислений. Оказывается, что для некоторых классов полиномов ответ отрицателен, для других он положителен, а в подавляющем большинстве случаев ответ неизвестен. Соответствующие вопросы, открытые в течении нескольких десятилетий, по праву числятся среди наиболее важных, интересных и трудных проблем современной теории сложности.

В настоящих лекциях мы, в частности, попытаемся рассказать о некоторых (или всех, если хватит времени) направлениях из следующего списка:
1. Nonscalar complexity (вариант сложности, в котором учитываются только умножения) и полиномы высокой степени.
2. Билинейная сложность и матричное умножение.
3. Определитель, перманент и теория алгебраической NP-полноты.

Разборов Александр Александрович — доктор физико-математических наук, член-корреспондент РАН.

Летняя школа «Современная математика», г. Дубна
24 июля 2010 г.

http://forany.xyz/a-232

Видео Алгебраическая сложность. Лекция 2 // Александр Разборов канала Научный канал