Главная Проекты Учеба Фото Авторы Гостевая книга Послать письмо автору

Контрольная работа по теории сложности

Вариант 3

1. Верно ли, что класс языков NP замкнут относительно операции объединения?

2. Является   ли   NP-полной   задача   «Минимизация   штрафа  за   невыполнение  работ  на  одном процессоре»? (Даны множество работ N={1,...,n}, длительность t_i, вес w_i и директивный интервал (b_i,f_i] для  каждой  работы  iI принадлежит N и  число  К.  Существует ли  однопроцессорное  расписание   t=(t₁,..., t_n) без прерываний    и    переключений    (t_i    -    момент    начала    выполнения    работы    i),    такое,    что   ?). Является ли эта задача со-NP-полной? При доказательстве NP-полноты можно пользоваться NP-полнотой только семи основных NP-полных задач.

3. Является ли NP-полной в сильном смысле задача 2?

4. Доказать, что оптимизационная задача «Рюкзак» (Заданы набор предметов N={1,...,n}, их объемы v_i  и стоимости s_i и объем рюкзака V. Найти подмножество предметов из N, имеющих максимальную суммарную стоимость и вмещающихся в рюкзак) является NP-трудной и NP-легкой.

5. Существует ли приближенный полиномиальный алгоритм   А   решения оптимизационной задачи «Независимое  множество»  (Дан  граф  G  =  (V,  А).  Найти  независимое  множество максимальной мощности) с оценкой r_A² <=K, где К - константа?