Дисциплина «Теоретические основы компьютерных наук» для аспирантов ФКН ВШЭ

2015-2016 год

Последний экзамен по курсу состоится в пятницу 23 июня 2017 г. в 10:30-13:30 в ауд. 511 (сдают М. Марон и Д. Тверской).

Пересдача коллоквиума и экзамена назначена на пятницу 7 октября с 9 до 11:50 (две пары) в ауд. 618. Можно пользоваться собственными рукописными конспектами (не ксерокопиями чужих), литературой пользоваться нельзя.

Программа экзамена

Программу коллоквиума см. ниже (список вопросов к коллоквиуму).

• Лекции и семинары происходят по средам
  13:40-16:30 в следующие дни:
  18 ноября ауд. 513, 16 декабря ауд. 513,
  10 февраля ауд. 402, 2 марта ауд. 402 (коллоквиум),
  23 марта ауд. 402, 20 апреля ауд. 402, 18 мая ауд. 402,
  25 мая ауд. 402.

• Оценка за курс есть сумма семи оценок: оценка за контрольную работу (1 балл),
  оценки за три домашних задания (по 1 баллу за каждое), оценки за коллоквиум, эссе и экзамен
  (по 2 балла каждая).

• Cроки сдачи.
  Эссе — 20 апреля, коллоквиум 2 марта в 13:30 (ауд. 402), домашние задания 10 февраля, 23 марта, 18 мая. Экзамен в середине июня.

Оценки

Домашние задания

• Первое домашнее задание надо сдать до 10 февраля, 13:30 МСК
  на листочках или послать по почте nikolay.vereshchagin@gmail.com в формате PDF.

• Второе домашнее задание надо сдать до 23 марта, 13:30 МСК
  на листочках или послать по почте nikolay.vereshchagin@gmail.com в формате PDF.

• Третье домашнее задание надо сдать до 18 мая, 13:30 МСК
  на листочках или послать по почте nikolay.vereshchagin@gmail.com в формате PDF.

Содержание лекций и семинаров

• Лекция 1. Многоленточные машины Тьюринга, время и память. Равнодоступные адресные
  машины, время память и длина машинного слова. Полиномиальная эквивалентность этих двух моделей
  (без доказательства). Классы P, DEXP и EXP, PF, DEXPF, EXPF.
  Теорема о иерархии по времени в простейшем виде:
  классы P, DEXP и EXP различны. Сводимость Карпа. DEXP трудность задачи эквивалентности
  расширенных регулярных выражений (без доказательства). Следствие: эта задача не
  принадлежит классу P.

• Семинар 1. Сведения различных задач друг к другу. Полиномиальные алгоритмы для
  2-раскраски и 2-КНФ.

• Лекция 2. Машины с оракулом и сводимость Кука, ее транзитивность и сохранение класса P.
  Вероятностные машины и классы BPP и PP. Амплификация. Схемы из функциональных
  элементов и класс nuP (P/poly). Включение P в nuP (P/poly) (без доказательства).
  Два определения класса NP.

• Семинар 2. Эквивалентность двух определений NP. Сводимость задач поиска и оптимизации
  к задачам из NP (на примере SAT, рюкзака, коммивояжера).

• Лекция 3. Доказательство включения P в nuP (P/poly). Теорема Кука-Левина об NP полноте
  задачи CIRCUIT-SAT. NP полнота задачи 3-CNF. NP полнота задачи SUBSET-SUM. NP полнота задач
  CLIQUE, INDEPENDENT_SET, VERTEX-COVER.
  Без доказательства: NP полнота задач 3-COLORING, HAMILTONIAN-CYCLE, 3-DIMENSIONAL-MATCHING.

  Класс #P (KP). #P полнота задач, соответствующих основным NP полным задачам (без доказательства).
  Теорема Вальянта о #P полноте задачи вычисления перманента (количества совершенных паросочетаний
  в двудольном графе), без доказательства.

• Семинар 3. Была контрольная работа на доказательства NP полноты и
  сводимость NP задач поиска к NP задачам разрешения.

• Лекция 4.

  PSPACE — определение с помощью МТ и РАМ.

  Вложение всех классов полиномиальной иерархии в PSPACE.

  TQBF и принадлежность этого языка PSPACE.

  Полиномиальные игры и принадлежность множества выигрышных
  позиций PSPACE.

  Обратное сведение: от PSPACE к полиномиальным играм.

  PSPACE полнота TQBF.

  Решение задачи s-t-связности для графов из 2^n
  вершин на памяти O(n^2).

  NPSPACE и теорема Сэвича.

  PSPACE полнота задачи об эквивалентности регулярных выражений
  (без доказательства).

  Оптимизационные задачи и их сводимость к задачам из NP

• Семинар 4.

  Сложность задачи об эквивалентности ДКА.

  Сведение задачи об эквивалентности регулярных выражений
  к задаче об эквивалентности НКА.

  Принадлежность PSPACE задачи об эквивалентности НКА и задачи об эквивалентности регулярных выражений.

  Приближенное решение оптимизационных задач: упаковка в контейнеры,
  вершинное покрытие.

• Лекция 5.

  Релаксация задач целочисленного линейного программирования, возникающих
  при сведении NP трудных задач к задаче ЦЛП (на примере задачи о
  вершинном покрытии).

  Задачи линейного программирования и выпуклого программирования. Метод эллипсоидов: поиск доступного
  решения и поиск глобального минимума функции на всем пространстве.

  Параметрические задачи. Класс FPT простых задач при фиксированном значении параметра. Принадлежность
  классу FPT задачи о вершинном покрытии. Сводимость параметрических задач. Класс W[1] и полные
  в нем задачи (без доказательства).

• Семинар 5. Доказательство того, что минимум в линейной
  программе, получаемой из задачи о вершинном покрытии состоит
  из полуцелых значений. Решение задачи о вершинном покрытии за время 2^k poly(n). Принадлежность
  FPT задачи о независимом множестве в планарных графах.

• Лекция 6. Парадигма PAC-learning. Оценка разницы между эмпирическим и
  настоящим качеством гипотез в терминах количества гипотез. Размерность Вапника-Червоненкиса.
  Теорема Вапника-Червоненкиса о разнице между эмпирическим и
  настоящим качеством гипотез. Лемма Зауэра-Шелаха.

• Семинар 6. Алгоритмы обучения целевой функции ограниченных классов:
  функции диктатора, функции x_i и (NOT x_i), общая оценка ошибки через длину выборки и
  количества возможных концепций, конъюнкции, элементарные конъюнкции. Вычисление VC-размерности
  для полупространств и 1-DNF (последнее не успели доделать до конца).

• Лекция 7. Boosting на примере теоремы Shapire об эквивалентности слабой и сильной
  изучаемости класса концепций.

• Семинар 7. PCP-теорема и ее применение к доказательству NP трудности
  задачи приближенного вычисления размера максимальной клики.
  Вычисление VC-размерности класса 1-DNF. Пример, показывающий, что
  класс 2-DNF имеет бОльшую размерность, чем класс 1-DNF.

Что надо изучить самостоятельно:

Ко второму занятию (16 декабря) необходимо самостоятельно ознакомиться со следующими темами:

• Теорема о полиномиальной эквивалентности машин Тьюринга с произвольным количеством лент
  и равнодоступных адресных машин. [2]
• О иерархии по времени и по памяти [6, глава 11]
• Доказательство DEXP трудности задачи об эквивалентости расширенных регулярных
  выражений [6, глава 11]
• Схемы из функциональных элементов, схемная сложность и экспоненциальная верхняя (O(n2^n))
  и нижняя (O(2^n/n) оценки сложности реализации булевых функций от n переменных в любом
  фиксированном базисе.

• Полиномиальные алгоритмы (для равнодоступных адресных машин) для вычисления НОД
  натуральных чисел, возведения данного числа в данную степень по данному модулю, решения
  сравнений вида ax=b (mod c). Извлечение корня данной степени из данного натурального числа (нужно
  найти целую часть корня).

К третьему занятию (10 февраля) необходимо
самостоятельно ознакомиться со следующими темами:

• Доказательство включения P в nuP (P/poly) [1]
• Уменьшение ошибки при повторении вероятностного алгоритма (amplification) [1]
• Класс RP и его включение в NP [8, параграф 7.3]

К четвертому занятию (2 марта), на котором состоится коллоквиум, необходимо
самостоятельно ознакомиться со следующими темами:

• Доказательство NP полноты задач 3-COLORING, HAMILTONIAN-CYCLE, 3-DIMENSIONAL-MATCHING.
• Полиномиальная иерархия [1,3,5]. Включение NP и всех классов полиномиальной
  иерархии в EXP.

• Полные задачи в классах полиномиальной иерархии [5, параграф 7.2].
• Замкнутость классов полиномиальной иерархии относительно сводимости Карпа.
• Включение BPP в P/poly и в Sigma_2 [1].
• #P полнота задач вычисления количества выполняющих наборов данной схемы из функциональных элементов
  и данной 3-CNF [5, параграф 7.3]
• Полиномиальный вероятностный алгоритм распознавания алгебраических тождеств. [8, параграф 7.2.3]
• Полиномиальный вероятностный алгоритм распознавания простоты числа. [1]

• Определение классов W[i] параметрических задач. Полнота задач о независимом множестве и
  Weighted s-CNF (при любом фиксированном s большем 1) в классе W[1]. По книге [7].

• Принадлежность FPT задач PLANAR DOMINATING SET, CLOSEST STRING. По книге [7].
• Симлекс метод решения задач линейного программирования. Лемма Фаркаша об отделении
  гиперплоскостью и теорема двойственности.
  Метод эллипсоидов решения задач выпуклого программирования:
  оценки объема эллипсоидов. По книге [8].

К шестому занятию (25 мая) необходимо
самостоятельно ознакомиться с принципом Ocсam’s razor машинного обучения,
прочитав статью [Blumer, A., Ehrenfeucht, A.,
Haussler, D., and Warmuth, M.K.(1987). Occam’s razor. Information Processing Letters,
24, 377-380.]

К экзамену (20 июня) необходимо самостоятельно разобрать доказательство
оценки вероятности отклонения эмпирического качества гипотез
от их фактического качества для гипотез из класса данной
размерности Вапника-Червоненкиса (теорема Вапника-Червоненкиса).

Список вопросов к коллоквиуму.

• Машины Тьюринга, равнодоступные адресные машины, вероятностные машины, недетерминированные машины.
• Теорема о полиномиальной эквивалентности машин Тьюринга с произвольным количеством лент и
  равнодоступных адресных машин.

• Полиномиальные алгоритмы (для равнодоступных адресных машин)
  для вычисления НОД натуральных чисел,
  возведения данного числа в данную степень по данному модулю,
  решения сравнений вида ax=b (mod c). Извлечение корня данной степени из данного натурального
  числа (нужно найти целую часть корня).

• Сложностные классы P, NP, BPP, RP, nuP (P/poly), #P, DEXP, EXP, полиномиальная
  иерархия.

• Доказательство DEXP трудности задачи об эквивалентости расширенных регулярных выражений.
• Схемы из функциональных элементов, схемная сложность и экспоненциальная
  верхняя (O(n2^n)) и нижняя (O(2^n/n))
  оценки сложности реализации булевых функций от n
  переменных в любом фиксированном базисе.

• Теорема о иерархии по времени и по памяти.
• Включение P в P/poly.
• Уменьшение ошибки при повторении вероятностного алгоритма (amplification).
  Включение BPP в P/poly.

• Полиномиальный вероятностный алгоритм распознавания алгебраических тождеств.
• Полиномиальный вероятностный алгоритм распознавания простоты числа.
• Теорема Кука-Левина об NP полноте задачи CIRCUIT-SAT.
• Доказательство NP полноты задач 3-CNF, SUBSET-SUM, CLIQUE,
  INDEPENDENT_SET, VERTEX-COVER, 3-COLORING, HAMILTONIAN-CYCLE, 3-DIMENSIONAL-MATCHING.

• Полиномиальная иерархия. Включение NP и всех классов полиномиальной
  иерархии в EXP.

• Полные задачи в классах полиномиальной иерархии.
• Включение BPP в Sigma_2.
• #P полнота задач вычисления количества выполняющих наборов данной схемы из функциональных элементов
  и данной 3-CNF.

Темы эссе (окончательный)

1. (Взято Михаилом Бочкарёвым)
   Simple NP problems whose counting version is #P complete (permanent and a couple of others).
   Примеры простых NP задачи, для которых задачи подсчета #P полны (перманент и пара других).
   Про перманент можно прочитать в учебнике Пападимитриу [11], надо изложить доказательство.

2. (Взято Анной Потапенко) One-way permutaions and constructing Pseudo random
   generators. Односторонние перестановки и их применение для построения генераторов псевдослучайных чисел.
   Можно прочитать в [9].

3. (Взято Дмитрием Фроловым)
   The combinatorial proof of PCP-theorem. Комбинаторное доказательство PCP-теоремы. По учебнику [9].

4. NP hardness of approximate solution of MAX3SAT via PCP-theorem.
   NP трудность приблизительного решения для MAX3SAT путем сведения к PCP-теореме.
   По учебнику [9].

5. (Тверской)
   DEXP hardness of deciding valididy of formulas of the elementary theory
   of the additive group of reals. Super-Exponential Complexity of Presburger Arithmetic.
   (Fischer — Rabin theorems).
   DEXP трудность задачи задачи распознавания истинности формул в абелевой группе
   действительных чисел. Трудность задачи распознавания истинности формул Арифметики
   Прессбургера (теоремы Фишера—Рабина).
   По статье [Fischer, Michael J.; Rabin, Michael O. (1974). «Super-Exponential Complexity of
   Presburger Arithmetic». Proceedings of the SIAM-AMS Symposium in Applied Mathematics 7: 27–41.]
6. NEXP=MIP (MIP is the class of languages that have two provers interactive protocols).
   Совпадение NEXP и MIP (класса языков, допускающих интерактивное доказательство с двумя
   Доказывающими).
   По статье [M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs:
   how to remove intractability,
   Proceedings of ACM STOC’88, pp. 113-131, 1988.]

7. (Взято Ильей Турунтаевым)
   Nisan — Wigderson generators with an
   application to extractors (Trevisan extractor).
   Генераторы Нисана-Вигдерсона и их применение для построения экстраторов (Тревисан). [9]
8. (Взято Нуртасом Махажановым) Expanding graphs
   and LOGSPACE algorithm for s-t-connectivity for undirected graphs (Reingold theorem).
   Экспандеры и их применение в алгоритме поиска пути в неорентированном графе на логарифмической
   памяти. [9]
9. (взято Андреем Шестаковым)
   Average case complexity and
   average case complete NP problems. Сложность в среднем и NP трудные в среднем задачи.
   [Andrej Bogdanov and Luca Trevisan:
   Average-case complexity. In Madhu Sudan, editor, Foundations and Trends in
   Theoretical Computer Science, volume 2, issue 1, Now Publishers, 2006.]
10. (Взято Екатериной Лобачевой) Yao XOR lemma and its three proofs.
    XOR лемма Яо об увеличении трудности предиката с помощью функции XOR и три ее доказательства.
    http://www.wisdom.weizmann.ac.il/~oded/COL/yao.pdf

11. Circuits of small depth: the classes NC, NC^1, AC^0, AC^0[m].
    Razborov-Smolensky theorem. Barrington theorem. (по книге [12])

12. (Взято Николаем Фединым)
    An Exponential lower bound for PARITY for constant depth AND-OR-circuits.
    (По работе [J. Håstad, Almost Optimal Lower Bounds for Small Depth Circuits, in Randomness and Computation, Advances in Computing Reasearch,
    Vol 5, ed. S. Micali, 1989, JAI Press Inc, pp 143-170].)

Литература

1. A. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо, 1999.

2. Владимир Крупский. Введение в сложность вычислений. Факториал Пресс, 2006.

3. Sipser M. Introduction to the Theory of Computation. — Cengage Learning, 2013.

4. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.

5. M. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.
   М. Мир 1979

7. Downey, Rod G.; Fellows, Michael R. (1999). Parameterized Complexity. Springer.

8. M. Grötschel, L. Lovász, A. Schrijver:
   Geometric Algorithms and Combinatorial Optimization, Springer, 1988.

   Продвинутая литература для написания эссе

9. Sanjeev Arora, Boaz Barak Computational Complexity: A Modern Approach.
   Cambridge University Press, 2009.

10. O. Goldreich. Foundations of Cryptography. Basic Tools. Cambridge UP. 2001.

11. Christos H. Papadimitriou,
    Computational Complexity (Addison Wesley, 1994)

12. H. Vollmer. Introduction tp Circuit Сomplexity. Springer 1999.