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

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

Вариант 4

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

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

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

4. Доказать, что оптимизационная задача «Клика» (Задан граф G = (V, А). Найти клику максимальной мощности) является NP-трудной и NP-легкой.

5. Существует ли приближенный полиномиальный алгоритм А решения задачи 4 с оценкой  r_A¹ <=К  где К- константа?