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

Срок сдачи 16 октября.

1. Построить одноленточную и двухленточную
машины Тьюринга, которые по слову x$y находят побитовую сумму x и y по модулю 2.
Слова x и y состоят из нулей и единиц и имеют одну длину.
Время работы одноленточной машины должно быть ограничено квадратичным
многочленом от длины входа, а двухлетночной — линейным.

2. Построить одноленточную и двухленточнцю
машины Тьюринга, которые по слову x$y, выясняют, входит ли x в у.
Слова x и y состоят из нулей и единиц.
Время работы обеих машин
должно быть ограничено квадратичным многочленом от длины входа.

Срок сдачи 23 октября.

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

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

Срок сдачи 6 ноября.

5. Свести (по Карпу) задачу СуммаПодмножества к задаче Разбиение,
и обратно. (Задача СуммаПодмножества: дан список натуральных чисел,
возможно с повторениями, и еще одно
натуральное число; надо узнать, можно ли это число представить в
виде суммы какого-то под-списка исходного списка, то есть, можно ли
выбросить некоторые числа из списка так, чтобы сумма оставшихся была равна данному
числу; числа задаются в двоичной записи. Задача Разбиение: дан набор натуральных
чисел; надо узнать, можно ли его разбить на две части так, чтобы суммы частей были одинаковы.)

6. Свести (по Куку) задачу о поиске изоморфизма двух графов к задаче распознавания, изоморфны ли данные графы.

Срок сдачи 13 ноября.

7. Свести (по Куку) задачу о существовании в данном графе гамильтонова цикла к задаче существования в данном графе гамильтонова пути (гамильтоновым путем в графе называется
путь по ребрам, проходящий ровно по одному разу через каждую вершину; начальная и конечная вершина пути могут совпадать, а могут и различаться).

8. Свести (по Карпу) задачу о расписании к задаче Разбиение (см. задачу 5). Задача о расписании:
дано некоторое множество заданий и для каждого задания указан временной интервал, в который
его надо решить и время, необходимое для его решения;
спрашивается можно ли составить расписание работы однопроцессорной машины так, чтобы все задания были решены.
Другими словами, дан набор троек натуральных чисел (a_i,b_i,c_i), i=1…n
(все числа даются в двоичной записи). Можно ли выделить на каждом интервале (a_i,b_i) подинтервал длины c_i так, чтобы
при разных i выделенные интервалы не пересекались?

Срок сдачи 20 ноября.

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

Исходное данное: Даны два графа.

Вопрос: Изоморфен ли первый граф некоторому пографу второго графа?

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

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

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

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

Срок сдачи 27 ноября.

В формулировке восьмой задачи была ошибка (нужно сводить в другую сторону)

8. Свести (по Карпу) к задаче о расписании задачу Разбиение (см. задачу 5). Задача о расписании: дано некоторое множество
заданий и для каждого задания указан временной интервал, в который
его надо решить и время, необходимое для его решения;
спрашивается можно ли составить расписание работы однопроцессорной машины так, чтобы все задания были решены.
Другими словами, дан набор троек натуральных чисел (a_i,b_i,c_i), i=1…n
(все числа даются в двоичной записи). Можно ли выделить на каждом интервале (a_i,b_i) подинтервал длины c_i так, чтобы
при разных i выделенные интервалы не пересекались?

11. Свести (по Куку) оптимизационный вариант задачи коммивояжера к
задаче разрешения КОММИВОЯЖЕР. Оптимизацинный вариант состоит в нахождении гамильтонова цикла наименьшей стоимости,
а задача разрешения — в выяснении, есть ли гамильтонов цикла стоимости не больше данного числа.

12. Пусть в задаче коммивояжера не требуется, чтобы коммивояжёр проходил каждый город не более одного раза (но
по-прежнему требуется, чтобы коммиояжер побывал в каждом городе и вернулся в исходный город). Доказать, что
полученная таким образом задача разрешения NP полна.

Срок сдачи 4 декабря.

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

14. Построить схему из функциональных элементов полиномиального от n
размера, которая по двум натуральным n битовым числам выдает 0 или 1 в
зависимости от того, какое число больше.

Срок сдачи 11 декабря.

15. Докажите, что класс BPP замкнут относительно дополнения, пересечения и объединения.

16. Докажите, что если язык A принадлежит классу BPP, а язык B сводится по Куку к языку A, то и
язык B принадлежит классу BPP.

Срок сдачи 18 декабря.

17. Рассмотрим множество схем из ФЭ, которые вычисляют некоторую сюръекцию между множеством
входных слов и множеством выходных слов (то есть, любое слово может появиться на выходе).
Докажите, что это множество принадлежит класу Пи-2 полиномиальной иерархии.

18. Докажите, что все классы полиномиальной иерархии замкнуты относительно пересечений и
объединений.

Результаты.

Тихонова 1+1 +1+0 +0.5+0 +0+0 +0.5+0.5 +0.5+0.5 +0+1 +0+0
Коротин 1+1 +1+1 +1+0 +1+1 +1+0.5 +1+1 +1+1 +1+1
Архипова 0.5+0.5 +0+0 +0+0 +0+1 +1+0 +1+1 +0.8+1 +0+0
Мелихова 1+1 +0+0 +1+0 +1+0 +0.5+0 +1+1 +0+0 +0.5+1
Митрущенкова 1+0 +1+1 +0.8+0 +1+0 +1+0 +1+1 +0+1 +1+0
Жуков 1+1 +0+0 +0+0 +1+1 +1+0.5 +0.5+1 +0+0 +0+0
Даровских 1+1 +1+1 +1+1 +0.5+0.5 +1+1 +0.3+0.5 +0+0 +0+0
Власенко 1+1 +1+1 +1+0 +1+0 +1+1 +0+0 +1+1 +0.7+1
Якушева 1+1 +0+0 +1+0 +0+0.8 +1+0 +1+0 +0+1 +0+1
Мирвахабова 1+0.5 +0+0
Николаев 1+0.5 +0+0
Малахова 0+0 +1+0 +0.5+0 +0+1 +1+0.5 +0+1 +0+1 +0+0