Алгебраическая сложность
Как грамотно вычислить значение полинома от многих переменных? Можно, конечно, посчитать по отдельности каждый входящий в него моном и результаты сложить, но нельзя ли придумать способ сэкономить на числе используемых операций хотя бы для некоторых наиболее важных и часто встречающихся полиномов?
Изучением таких вопросов как раз и занимается теория алгебраической сложности вычислений. Оказывается, что для некоторых классов полиномов ответ отрицателен, для других он положителен, а в подавляющем большинстве случаев ответ неизвестен. Соответствующие вопросы, открытые в течении нескольких десятилетий, по праву числятся среди наиболее важных, интересных и трудных проблем современной теории сложности.
В настоящих лекциях мы, в частности, попытаемся рассказать о некоторых (или всех, если хватит времени) направлениях из следующего списка:
- Nonscalar complexity (вариант сложности, в котором учитываются только умножения) и полиномы высокой степени.
- Билинейная сложность и матричное умножение.
- Определитель, перманент и теория алгебраической NP-полноты.
Разборов Александр Александрович, доктор физико-математических наук, член-корреспондент РАН.
Летняя школа «Современная математика», г. Дубна, 23-24 июля 2010 г.
Похожее
-
Александр Разборов
Пожалуй ни одно другое достижение современной теории сложности вычислений не вызывает такого живого интереса и не менее яростных споров как модель квантовых вычислений. Предметом дискуссии, однако, в основном является возможность физической реализации квантового компьютера, чего мы, к счастью, касаться не будем. Вместо этого мы попробуем разобраться в чисто математических аспектах этой модели и, в частности, постараемся пройти столько из нижеследующего, сколько позволит время: Классические и квантовые схемы; Алгоритм Шора быстрого разложения чисел на множители: основные идеи; Квантовые оракулы и задача о скрытой подгруппе; Алгоритм квантового поиска Гровера.
-
Александр Разборов
Теория сложности вычислений — бурно развивающаяся область теоретической информатики (theoretical computer science) и охватывает как чисто теоретические вопросы, так и вопросы, непосредственно связанные с практикой. Среди наиболее важных приложений этой теории можно назвать способы построения и анализа эффективных алгоритмов, а также современные криптографические методы. Поэтому знакомство с основами теории сложности, безусловно, полезно любому, кто собирается серьезно заниматься практическим программированием или теоретическими исследованиями.
-
Владимир Успенский
Составленная из нулей и единиц цепочка 100010111011110100000111 выглядит более случайной, чем цепочка 010101010101010101010101. Возможно ли разделить все цепочки нулей и единиц на случайный и не случайные? Для конечных цепочек эта задача вряд ли осуществима. Однако можно пытаться решать её для бесконечных цепочек, т.е. для последовательностей. Иными словами, можно пытаться найти строгое математическое определение для понятия «случайная последовательностей нулей и единиц».
-
Александр Шень
Природа статистических законов вызывала споры с самого рождения теории вероятностей и продолжает их вызывать. Эти философские споры привели к рождению интересной математической теории: алгоритмической теории вероятностей и информации, которая — в отличие от классической — пытается дать определение индивидуального случайного объекта. Мы обсудим основные понятия этой теории и их связь с основаниями и парадоксами теории вероятностей. Об этом в публичной лекции математика Александра Шеня, кандидата физико-математических наук, старшего научный сотрудник Лаборатории теории передачи информации и управления ИППИ РАН.
-
Четыре тысячи лет назад жители Вавилонии изобрели умножение. А в марте этого года математики усовершенствовали его. 18 марта 2019 два исследователя описали самый быстрый из известных методов перемножения двух очень больших чисел. Работа отмечает кульминацию давнишнего поиска наиболее эффективной процедуры выполнения одной из базовых операций математики. «Все думают, что метод умножения, который они учили в школе, наилучший, но на самом деле в этой области идут активные исследования», — говорит Йорис ван дер Хувен, математик из Французского национального центра научных исследований, один из соавторов работы.
-
Аскольд Хованский
Сколько вещественных корней имеет заданный полином с вещественными коэффициентами? Замечательная теорема Штурма дает исчерпывающее решение этой задачи. “Теорема, имя которой я имею честь носить”, – так говорил об этом результате Штурм, который считал его главным достижением своей жизни. Совместна ли заданная система полиномиальных уравнений и неравенств от нескольких вещественных переменных? Теорема Зайденберга–Тарского, отвечающая на этот вопрос, является грандиозным многомерным обобщением теоремы Штурма. В лекциях будет рассказано новое наглядное решение задачи Штурма. Оно несложно переносится на многомерный случай и приводит к доказательству теоремы Зайденберга–Тарского.
-
Владимир Тихомиров
Энтропия — мера неопределённости, мера хаоса. В естественных науках это мера беспорядка системы, состоящей из многих элементов; в теории информации — мера неопределённости какого-либо опыта, процесса или испытания, которые могут иметь разные исходы (а значит, мера количества информации); в математике — мера сложности объекта или процесса. Понятие энтропии было впервые введено в 1865 году Р. Клаузиусом в термодинамике, К. Шенноном в теории информации в 1949 г., в теории стохастичпеских процессов Колмогоровым, Гельфандом и Яглом в 1956 г., в функциональном анализе и теории динамических систем Колмогоровым в 1956–1958 гг. Между мирами полной детерминированности, изучаемой классическим анализом и миром хаоса, изучаемым теорией вероятностей, ныне перекидывается мост, который связан с понятием энтропии.
-
Иван Оселедец
Возможно ли в линейной алгебре получение новых результатов? Почему в университетах этот курс учат неправильно? Какое матричное разложение является самым важным? Об умножении матрицы на вектор, быстрых алгоритмах и сингулярном разложении. рассказывает доктор физико-математических наук Иван Оселедец.
-
Николай Адрианов
В этом курсе мы познакомимся с замечательной теорией NP-полных задач. Проблема (не)равенства классов P и NP — одна из «задач тысячелетия», за каждую из которых объявлен приз в миллион долларов. Мы разберемся в определении класса NP и научимся доказывать NP-полноту различных комбинаторных задач (классические теоремы Кука–Левина и Карпа). Особое внимание уделим задаче выполнимости булевых формул SAT. Мы поиграем с программами, решающими эту задачу, разберем какие алгоритмы они используют, как результатом их работы может быть доказательство, допускающее автоматическую проверку. Научимся сводить логические головоломки и математические задачи к SAT, поговорим о судоку, задачах теории Рамсея, недавнем продвижении в задаче о хроматическом числе плоскости и о «самом большом математическом доказательстве».
-
Алексей Сосинский
В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта. Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.
Далее >>>
|
|
