Introduction to computational complexity theory
September 15–December 29, 2020, MIPT - MI RAS, Moscow
Introduction to computational complexity theory, Moscow, September 15–December 29, 2020
-
Занятие 7. NP-полнота следующих задач: NAE-3-SAT, 3-COL, SUBSET-SUM, CLIQUE, VERTEX-COVER
V. V. Podolskii
November 3, 2020 16:15
Moscow, MIPT - MI RAS
-
Занятие 6. Соотношение между классами P и P/poly. Задача CIRCUIT-SAT, ее NP-полнота. Задача 3-SAT, ее NP-полнота. Задача IND-SET, ее NP-полнота
V. V. Podolskii
October 27, 2020 16:15
Moscow, MIPT - MI RAS
-
Занятие 5. Булевых схемы. Примеры: сложение, умножение, связность. Верхняя и нижняя оценки сложности вычисления булевых функций булевыми схемами
V. V. Podolskii
October 20, 2020 16:15
Moscow, MIPT - MI RAS
-
Занятие 4. Класс NP, примеры. Соотношение с классами P и PSPACE. Недетерминированные машины Тьюринга, второе определение класса NP, эквивалентность определений. Полиномиальные сводимости, их основные свойства. NP-трудность и NP-полнота, их основные свойства
V. V. Podolskii
October 13, 2020 16:15
Moscow, MIPT - MI RAS
-
Занятие 3. Теоремы об иерархии по времени и по памяти
V. V. Podolskii
October 6, 2020 16:15
Moscow, MIPT - MI RAS
-
Занятие 2. Связь одноленточных и многоленточных машин Тьюринга. Универсальная машина Тьюринга. Вычисления с ограничением на время и память. Классы P, PSPACE, EXP. Примеры полиномиально вычислимых функций и полиномиально разрешимых языков
V. V. Podolskii
September 29, 2020 16:15
Moscow, MIPT - MI RAS
-
Занятие 1. Машины Тьюринга, вычисление функций на машинах Тьюринга, лемма об очистке мусора, многоленточные машины Тьюринга
V. V. Podolskii
September 22, 2020 16:15
Moscow, MIPT - MI RAS
-
Занятие 0. Устройство курса правила оценивания. Краткий обзор основ сложности вычислений. Классы с ограничением на память. Класс PSPACE, его свойства. Задача TQBF является PSPACE-полной. PSPACE=NPSPACE
V. V. Podolskii
September 15, 2020 16:15
Moscow, MIPT - MI RAS
© , 2026
Seminar organizer