Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  


Introduction to computational complexity theory
September 15–December 29, 2020, MIPT - MI RAS, Moscow

RSS: Forthcoming seminars

Seminar organizer
Podolskii Vladimir Vladimirovich

Institutions
Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
Steklov Mathematical Institute of Russian Academy of Sciences, Moscow
Steklov International Mathematical Center


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
  
 
Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021