Александр Александрович Разборов
Сложность доказательств
А. А. Разборов планирует провести 2–3 занятия.
Доступны 3 видеозаписи курса.
- 1. Имеется выражение, состоящее из булевых переменных $p_1,\ldots,p_n$ и логических связок $\neg,\lor,\land,\Rightarrow$. Как доказать, что оно выполнимо, т. е. что вместо $p_1,\ldots,p_n$ можно подставить TRUE или FALSE так, что значение всего выражения окажется равным TRUE? Ответ очевиден: предъявить подстановку и проверить её прямым вычислением.
- 2. А как быстро доказать, что данное булево выражение невыполнимо? Короткого доказательства, скорее всего, не существует. Однако можно попытаться вывести противоречие из имеющихся аксиом с помощью хорошо известных в математической логике правил вывода.
- 3. А как доказать, что компьютерный чип или программа удовлетворяют требуемым спецификациям? Ответ: закодировать этот факт в виде булевого выражения, после чего воспользоваться алгоритмами, разработанными для предыдущей задачи.
- 4. Наконец, пусть имеется система полиномиальных уравнений или неравенств. Как доказать, что она несовместна? Ответ: воспользоваться теоремой Гильберта о нулях или её вещественным аналогом, известным как Positivestellensatz. Короткими при этом будут считаться доказательства, использующие исключительно полиномы малой степени.
Общим для всех этих ситуаций является то, что нас интересует не только наличие доказательства верных фактов (скажем, теорем), но и то, насколько «простым» оно может или не может быть. Несмотря на кажущуюся разнородность всех этих вопросов, их изучение в рамках одной дисциплины оказывается весьма продуктивным, и именно об этом мы и поговорим.
Специальных знаний для понимания курса не требуется, хотя самое общее представление о пропозициональной (булевой) логике было бы полезно. > Общим для всех этих ситуаций является то, что нас интересует не только наличие доказательства верных фактов (скажем, теорем), но и то, насколько «простым» оно может или не может быть. Несмотря на кажущуюся разнородность всех этих вопросов, их изучение в рамках одной дисциплины оказывается весьма продуктивным, и именно об этом мы и поговорим.
Специальных знаний для понимания курса не требуется, хотя самое общее представление о пропозициональной (булевой) логике было бы полезно.
Программа курсов и семинаров МЦНМО-НМУ в весеннем семестре 2024/2025 года
Расписание занятий в этом семестре
Курсы, читавшиеся в НМУ в разные годы (All Courses)
Если не указано иное, то начало занятий 7 февраля 2025.
Все обязательные курсы, почти все спецкурсы и некоторые доклады на спецсеминарах будут записываться на видео. Они будут доступны на общедоступном ресурсе.
К ВИДЕО-записям курсов этого семестра
Обязательные курсы
Первый курс
- Константин Валерьевич Логинов
- Алгебра-2
- читается по понедельникам с 17:30, очно+трансляция.
- Георгий Черных
- Топология-1
- читается по четвергам с 17:30, очно+трансляция.
- Олег Карлович Шейнман
- Математический анализ-2
- читается по пятницам с 17:30, очно+трансляция.
Второй курс
- Тарас Евгеньевич Панов
- Топология-3
- читается по понедельникам с 17:30 (семинары с 19:20), очно+трансляция
- Алексей Викторович Пенской
- Дифференциальная геометрия
- читается по средам с 17:30 (семинары с 19:20), очно+трансляция
- Алексей Игоревич Ильин
- Алгебра-4 (Группы и алгебры Ли)
- читается по четвергам с 17:30, очно+трансляция.
Список спецкурсов и спецсеминаров в весеннем семестре 2024/2025 года
- Михаил Юрьевич Розенблюм
- Алгебраическая теория чисел: введения. Продолжение годового спецкурса
- Денис Николаевич Терешкин
- Аддитивные и абелевы категории. Спецкурс рекомендован для 3-5 курсов.
- Константин Валерьевич Логинов
- Введение в ограниченность многообразий Фано. Спецкурс рекомендован для 3-5 курсов.
- Георгий Игоревич Шарыгин
- Циклические гомологии и их применения. Спецкурс рекомендован для 3-5 курсов.
- Андроник Арамович Арутюнов
- Грубая геометрия. Спецкурс в формате лекция + семинар, рекомендован для 3-5 курсов.
- Андрей Дмитриевич Рябичев
- Введение в поверхности бесконечного типа. Спецкурс рекомендован для 3-5 курсов.
- Георгий Борисович Шабат
- Тэта-функции и решетки. Часть 2. Спецкурс рекомендован для 3-5 курсов.
- Тарас Евгеньевич Панов
- Торическая топология, комбинаторика и теория гомотопий. Спецсеминар
- Георгий Игоревич Шарыгин и др.
- Деформационное квантование и квантовые группы. Спецсеминар
- А.М.Вербовецкий и И.С.Красильщик
- Когомологические аспекты геометрии дифференциальных уравнений,
руководители А.М.Вербовецкий и И.С.Красильщик - Николай Германович Мощевитин
- Диофантовы приближения. Спецсеминар рекомендован для 3-5 курсов
- Владимир Олегович Медведев
- Геометрия общей теории относительности. Спецкурс совместно с матфаком ВШЭ, рекомендован для 3-5 курсов.
- Алексей Викторович Пенской
- Риманова геометрия. Спецкурс совместно с матфаком ВШЭ, рекомендован для 3-5 курсов.
- Александр Борисович Калмынин
- Методы решета. Спецкурс рекомендован для 3-5 курсов.
- Алексей Викторович Пенской
- Спектральная геометрия. Спецсеминар рекомендован для 3-5 курсов.