|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.mccme.ru/dubna/2010/courses/razborov.htm
Дата изменения: Sat Jun 19 18:31:48 2010 Дата индексирования: Sun Sep 12 11:51:23 2010 Кодировка: koi8-r Поисковые слова: п п п п п п п п п п п п п п п п п п п п п |
| На главную страницу ЛШСМ-2010 | К списку курсов ЛШСМ-2010 |
Александр Александрович РазборовАлгебраическая сложностьА.А.Разборов планирует провести 2 занятия. |
 |
Как грамотно вычислить значение полинома от многих переменных? Можно, конечно, посчитать по отдельности каждый входящий в него моном и результаты сложить, но нельзя ли придумать способ сэкономить на числе используемых операций хотя бы для некоторых наиболее важных и часто встречающихся полиномов?
Изучением таких вопросов как раз и занимается теория алгебраической сложности вычислений. Оказывается, что для некоторых классов полиномов ответ отрицателен, для других он положителен, а в подавляющем большинстве случаев ответ неизвестен. Соответствующие вопросы, открытые в течении нескольких десятилетий, по праву числятся среди наиболее важных, интересных и трудных проблем современной теории сложности.
В настоящих лекциях мы, в частности, попытаемся рассказать о некоторых (или всех, если хватит времени) направлениях из следующего списка.
- Nonscalar complexity (вариант сложности, в котором учитываются только умножения) и полиномы высокой степени.
- Билинейная сложность и матричное умножение.
- Определитель, перманент и теория алгебраической NP-полноты.
