Задачи по курсу «Сложность вычислений»

Срок сдачи — 5 октября

1. Постройте одноленточную машину Тьюринга,
которая по двум n-битовым натуральным
числам x,y за время O(n^2) выясняет, какое число больше.

2. Постройте одноленточную машину Тьюринга,
которая по двум n-битовым натуральным
числам x,y за время O(n^2) находит их произведение.

3. Докажите, что существует функция с двумя значениями, вычислимая на памяти O(n2^n), но не вычислимая
на памяти O(2^n) (для многоленточных машин Тьюринга).

Срок сдачи — 12 октября

4. Докажите, что задача распознавания выполнимости формул (составленных
из переменных, пробегающих 0,1 и логических связок И, ИЛИ, НЕ, ИМПЛИКАЦИЯ)
сводится по Куку к задаче распознавания выполнимости формул в конъюнктивной
нормальной форме.

5. Докажите, что задача распознавания выполнимости формул в
дизъюнктивной нормальной форме разрешима за полиномиальное время.

Срок сдачи — 19 октября

6. Докажите, что задача выяснения, является ли алгебраическое выражение (с целыми коэффициентами,
знаками сложения и умножения, и скобками) не тождественно нулевым (то есть, принимающим ненулевое
значение при некоторых действительных значениях переменных) принадлежит NP.

7. Докажите, что если P=NP, то по любому графу можно не только выяснить, раскрашиваем ли он
в три цвета, но и найти раскраску, если она существует.

Срок сдачи — 26 октября

8. Докажите, что задача распознавания раскрашиваемости графа в два цвета принадлежит P.

9. Докажите, что задача СуммаПодмножества в единичной кодировке принадлежит P (исходные
числа задаются в унарной системе счисления, то есть, число n задается последовательностью
из n единиц).

Срок сдачи — 2 ноября

10. Докажите NP полноту задачи о разбиении: дан набор натуральных чисел
x_1, … , x_n (в двоичной записи); надо выяснить, можно ли разбить его
на две части с одинаковой суммой, то есть, существует ли такое множество
индексов I, для которого сумма чисел x_i с индексами i из I равна
сумме остальных чисел.

11. Докажите, что задача о поиске гамильтонова цикла в данном графе сводится
по Куку к задаче разрешения ГамильтоновЦикл (есть ли в данном графе гамильтонов
цикл). В доказательстве нельзя пользоваться NP полнотой последней задачей.

Срок сдачи — 9 ноября

12. Докажите NP-полноту следующей проблемы.

Исходное данное: Конечное семейство
конечных множеств (состоящих из натуральных чисел) и натуральное $k$.

Вопрос: Существует ли подсемейство,
состоящее из $k$ попарно непересекающихся
множеств?

В этой задаче и следующей разрешается использовать
без доказательства NP-полноту
задач 3-КНФ, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, 3-РАСКРАСКА,
СУММА ПОДМНОЖЕСТВА, ГАМИЛЬТОНОВ ЦИКЛ.

13. Докажите NP-полноту следующей проблемы.

Исходное данное: конечный граф $G$,
подмножество $R$ множества его вершин
и натуральное $k$.

Вопрос: существует ли в $G$ поддерево из не более, чем $k$ ребер,
включающее все вершины из $R$ (деревом называется связный граф без циклов,
поддеревом в $G$ называется любое дерево,
все ребра которого принадлежат $G$)?

Срок сдачи — 16 ноября

14. Докажите, что если языки A и B принадлежат BPP, то и их
пересечение, объединение и разность принадлежат BPP.

15. Докажите, что BPPF включено в PSPACEF. То есть, если некоторая функция,
отображающая двоичные слова в двоичные слова, вычисляется полиномиальной
по времени вероятностной машиной Тьюринга с вероятностью ошибки менее
1/3 на любом входе, то
эта функция вычисляется машиной Тьюринга на полиномиальной памяти.

Срок сдачи — 23 ноября

16. Докажите, что пересечение и объединение двух языков из \Sigma_n принадлежит \Sigma_n (для любого n).

17. Будем называть набор гирь n-представительным, если любое n-битовое число может быть
представлено суммой гирь этого набора (веса гирь — натуральныые числа и даны в двоичной записи).
Какому классу полиномиальной иерархии принадлежит множество n-представительных наборов гирь
(n есть часть входа задачи)?

Срок сдачи — 30 ноября

18. Докажите, что для любого i следующие три утверждения равносильны:
(1) \Sigma_i=\Pi_i, (2) \Sigma_i=\Sigma_{i+1}, (3) \Sigma_i=\Sigma_{k} для всех
k>i.

19. Рассмотрим следующую задачу. Дан граф G и некоторое
подмножество S множества его вершин. Требуется выяснить,
продолжается ли любая корректная раскраска
множества S в три цвета до корректной раскраски всего графа G в три цвета.
В каком классе полиномальной иерархии полна эта задача (ответ обосновать)?

Срок сдачи — 7 декабря

Рассмотрим следующую задачу. Дана схема С из функциональных элементов с
2n входами и одним выходом.
Сопоставим со схемой ориентированный граф G_C, вершинами которого
являются двоичные слова длины n, причем из вершины x
в вершину y направлена дуга тогда и
только тогда, когда схема C на входе xy выдает единицу.
Требуется узнать, есть ли в этом графе ориентированный путь из
вершины 00….0 в вершину 11…1.

20. Докажите, что эта задача полна в NPSPACE относительно сводимости Карпа.

21. Докажите, что эта задача лежит в PSPACE (то есть, разрешима на
полиномиальной памяти).

Срок сдачи — 14 декабря

22. Постройте оракул, для которого NP не равно CoNP.

23. Докажите, что если инъективная функция, сохраняющая длину,
вычислима на полиномиальной
памяти, то и обратная к ней также вычислима на полиномиальной памяти.

Срок сдачи — 29 февраля

24. Докажите, что множество булевых формул в базисе AND, NOT, OR, имеющих нечетное количество
выполняющих присваиваний, является ParityP полным языком.

25. Докажите, что любая функция из #P сводится по Куку к некоторому языку из PP.
(Напоминание: класс PP определяется, как множество языков вида {x| Prob[M(x)=1]>0.5},
где M некоторая вероятностная полиномиальная машина.)

Срок сдачи — 14 марта

26. Докажите, что множество схем из функиональных элементов AND, NOT, OR, у которых несколько входов и один выход и у которых более половины входных
присваиваний являются выполняющими, является PP полным языком.

27. Докажите, что дополнение языка из класса PP также принадлежит классу PP.

Срок сдачи — 21 марта

28. Постройте полиномиальный алгоритм, который находит в данном графе
вершинное покрытие мощности не более чем в 2 раза превосходящей мощность
наименьшего вершинного покрытия.

29. Докажите, что множество пар натуральных
чисел вида (x,m), где x не является квадратичным
вычетом по модулю m и взаимно просто с m, принадлежит IP(секр). Числа
заданы в двоичной записи. (Указание.
1. Без доказательства можно использовать то, что
доля взаимно простых с m вычетов не меньше
1/polylog m. 2. На самом деле этот язык принадлежит даже NP.)

Срок сдачи — 28 марта

30. Докажите, что NP^{BPP} включено в MA. Пояснение: NP^{BPP} обозначает объединение
семейств языков NP^A по всем языкам A из BPP.

Срок сдачи — 4 апреля

31. Пусть на множестве слов длины n задана некоторая полиномиально вычислимая бинарная операция,
для которой выполнены аксиомы абелевой группы. Тем самым для каждого n задана абелева
группа G_n. Рассмотрим множество таких кортежей (a_1,…,a_k), для которых для некоторого
n все a_1,…,a_k принадлежат G_n и порождают всю группу G_n. Докажите, что это множество
принадлежит IP(откр).

Срок сдачи — 18 апреля

32. Пусть множество A слов длины k разбито на N подмножеств. Докажите, что
найдётся такое l, для которого количетство подмножеств мощности 2^l или выше,
не меньше |A|/(k2^{l+1})

33. Докажите, что любой язык, имеющий интерактивное доказательство
с секретнымми случайными битам в два раунда (первое сообщение
пысылает Артур, а второе Мерлин), имеет также интерактивное доказательство
с открытыми случайными битами в пять раундов (первое, третье и пятое
сообщения пысылает Мерлин, второе и четвертое — Артур).

Срок сдачи — 25 апреля

34. Докажите, что MA включено в AM (здесь MA обозначает класс языков, имеющих интерактивное
доказательство с открытыми битами в два раунда, где первым посылает сообщение Мерлин,
а AМ — класс языков, имеющих интерактивное
доказательство с открытыми битами в два раунда, где первым посылает сообщение Артур).
[Указание. Можно использовать то обстоятельство, что в MA протоколах вероятность
ошибки можно сделать значительно меньше, чем общее количество возможных сообщений
Мерлина.]

35. Пусть язык A принадлежит BPP.
Докажите, что в этом случае существует MА протокол для языка А c
односторонней ошибкой (в случае, когда исходное
слово принадлежит языку, ошибка исключена).
Указание. Вспомните, как доказывалось включение BPP в Sigma2.

Срок сдачи — 16 мая

36. Пусть язык A принадлежит AM.
Докажите, что в этом случае существует АM протокол для языка А c
односторонней ошибкой (в случае, когда исходное
слово принадлежит языку, ошибка исключена).

37. Докажите, что существует оракул A, относительно которого
ParityP не включено в BPP.

Срок сдачи — 23 мая

38. Постройте РАМ, которая определяет, есть ли в графе вершинное покрытие
размера k за 2^k poly(n) шагов.