Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/~anromash/courses/fizteh-complexity-2009.pdf Дата изменения: Wed Mar 21 14:44:26 2012 Дата индексирования: Tue Oct 2 18:34:19 2012 Кодировка: Windows-1251 Поисковые слова: вторая космическая скорость

МФТИ, бакалавриат ФИВТ 2009, весенний семестр

Программа курса Сложность вычислений
Д.В. Мусатов, А.Е. Ромащенко

1. Многоленточные машины Тьюринга. Диагональная конструкция: существование невычислимых функций. 2. Основные сложностные классы: P, EXPTIME, PSPACE. 3. Теоремы об иерархии по времени и по зоне. 4. Недетерминированные вычисления, класс NP. 5. Сводимость по Карпу и сводимость по Куку. Понятие NP-полной и NPтрудной задачи. 6. Теорема ЛевинаКука о NP-полноте задачи SAT. 7. Примеры NP-полных задач: 3КНФ, 3-раскраска, Вершинное покрытие, Клика, Гамильтонов цикл. 8. Схемы из функциональных элементов. Схемная сложность задач Parity и Ma jority. Вычисление суммы двух n-битовых чисел схемой логарифмической глубины и линейной сложности. 9. Два определение класса P / poly, их эквивалентность. 10. Полиномиальная иерархия. 11. Теорема Сэвича. PSPACE-полнота задачи БФК. 12. Вычисления на логарифмической памяти, классы L и NL. NL-полнота задачи PATH. 13. NL = coNL. 14. Вероятностные машины Тьюринга, классы BPP, RP, ZPP. Теорема об уменьшении вероятности ошибки. 15. Вероятностный алгоритм Рабина проверки простоты числа. 16. Теорема о вложени BPP в P / poly. 17. Теорема Гача: BPP p p . 2 2 18. Детерминированный и вероятностный коммуникационные протоколы вычисления предиката равенства. 19. Построение оракулов A и B таких, что PA = NPA и PB = NPB . 20. Интерактивные доказательства. Задача Неизоморфизм-графов принадлежит классу IP. 21. Интерактивные протоколы с открытым датчиком случайных чисел; эквивалентность определений с секретными и открытыми датчиками случайных чисел: AM[poly] = IP[poly]. 22. IP = PSPACE. 23. Доказательства с нулевым разглашением. ZKP-протокол для задачи Изоморфизм-графов.

1


24. Вероятностно проверяемые доказательства, класс PCP(r, q ). Формулировка PCP-теоремы.
Список литературы.

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979 2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 3. Sipser. M. Introduction to the Theory of Computation. (Thomson course technology). 4. Arora S., Barak B. Computational Complexity: A Modern Approach. (Cambridge University Press).
Задачи для подготовки к экзамену.

1. Докажите, что следующие задачи распознавания принадлежат классу P: связный граф; граф без треугольников; двудольный граф; a, b, n, p такие, что an = b mod p (числа a, b, n, p даны в двоичной записи) 2. Постройте схему сложености O(n) для вычисление функции большинста n булевых значений maj ority (x1 , . . . , xn ). 3. L = {M : машина на всяком входе длины n останавливается за 100n3 шагов} Принадлежит ли этот язык P? PSPACE? 4. Обозначим
E X P C OM = { M , x, 1
n

: машина M на входе x останавливается за 2n шагов}

5. 6. 7. 8. 9. 10. 11. 12. 13. 14.

15. 16.

17.

Докажите, что PE X P C OM = NPE X P C OM = EXPTIME. Докажите, что проблема остановки NP-трудна, но не NP-полна. Докажите, что задача Гамильтонов-путь NP-полна. Time(2n ) = Time(22n ) NTime(n) = PSPACE Обозначим UCYCLE класс всех неориентрованных графов, в которых есть цикл. Докажите, что UCYCLE принадлежит классу L. Докажите, что язык 2SAT лежит в NL. Если PA = NPA то PHA = NPA . Если NEXPTIME = EXPTIME то P = NP. Если NP BPP то NP = RP. X O =позиции в игре крестики-нолики на конечных квадратных досках, в которых у крестиков есть выигрышная стратегия (для выигрыша нужно поставить 5 крестиков подряд). Докажите, что X O PSPACE Придумайте интерактивное доказательство для свойства x есть квадратичный невычет по модулю n (не используя теорему IP = PSPACE). Придумайте протокол с нулевым разглашением (со статистически точным моделированием журнала протокола) для свойства x есть квадратичный вычет по модулю n. Если PSPACE P / poly, то PSPACE = AM[1] (AM[1] игры Артура и Мерлина с 1-раундовым протоколом)

2