2022/2023
Научно-исследовательский семинар "Модальные логики и вычислительная сложность"
Статус:
Дисциплина общефакультетского пула
Кто читает:
Факультет математики
Когда читается:
1, 2 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Преподаватели:
Рыбаков Михаил Николаевич
Язык:
русский
Кредиты:
3
Контактные часы:
32
Программа дисциплины
Аннотация
В курсе затрагиваются два больших направления математики -- модальная логика и теория вычислительной сложности. Предполагается, что слушатели смогут не только познакомиться с понятиями, теоремами и вопросами этих разделов, но и увидят взаимосвязи между ними. Цель курса во многом ознакомительная и обзорная, хотя приводимые утверждения будут сопровождаться доказательствами. Во-первых, это знакомство с модальными языками и исчислениями, с реляционной семантикой возможных миров, с методами доказательства полноты и разрешимости логических систем, с теоремами о взаимосвязях между классическими и неклассическими логиками. Во-вторых, это знакомство с подходами к оценке сложности алгоритмов и задач, знакомство с классами сложности, с их взаимосвязями, с открытыми проблемами (включая проблему тысячелетия "P=NP?"). В-третьих, это знакомство с взаимосвязями между логикой и теорией вычислительной сложности, причём взаимосвязи предполагается показать как для классических логик, так и для модальных.