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
	November 3, 2020 (Tue)
1.	Занятие 7. NP-полнота следующих задач: NAE-3-SAT, 3-COL, SUBSET-SUM, CLIQUE, VERTEX-COVER V. V. Podolskii November 3, 2020 16:15, Moscow, MIPT - MI RAS
	October 27, 2020 (Tue)
2.	Занятие 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
	October 20, 2020 (Tue)
3.	Занятие 5. Булевых схемы. Примеры: сложение, умножение, связность. Верхняя и нижняя оценки сложности вычисления булевых функций булевыми схемами V. V. Podolskii October 20, 2020 16:15, Moscow, MIPT - MI RAS
	October 13, 2020 (Tue)
4.	Занятие 4. Класс NP, примеры. Соотношение с классами P и PSPACE. Недетерминированные машины Тьюринга, второе определение класса NP, эквивалентность определений. Полиномиальные сводимости, их основные свойства. NP-трудность и NP-полнота, их основные свойства V. V. Podolskii October 13, 2020 16:15, Moscow, MIPT - MI RAS
	October 6, 2020 (Tue)
5.	Занятие 3. Теоремы об иерархии по времени и по памяти V. V. Podolskii October 6, 2020 16:15, Moscow, MIPT - MI RAS
	September 29, 2020 (Tue)
6.	Занятие 2. Связь одноленточных и многоленточных машин Тьюринга. Универсальная машина Тьюринга. Вычисления с ограничением на время и память. Классы P, PSPACE, EXP. Примеры полиномиально вычислимых функций и полиномиально разрешимых языков V. V. Podolskii September 29, 2020 16:15, Moscow, MIPT - MI RAS
	September 22, 2020 (Tue)
7.	Занятие 1. Машины Тьюринга, вычисление функций на машинах Тьюринга, лемма об очистке мусора, многоленточные машины Тьюринга V. V. Podolskii September 22, 2020 16:15, Moscow, MIPT - MI RAS
	September 15, 2020 (Tue)
8.	Занятие 0. Устройство курса правила оценивания. Краткий обзор основ сложности вычислений. Классы с ограничением на память. Класс PSPACE, его свойства. Задача TQBF является PSPACE-полной. PSPACE=NPSPACE V. V. Podolskii September 15, 2020 16:15, Moscow, MIPT - MI RAS