Доказательство нп-полноты

Question

Покажите, что следующая проблема является NP-полной.

Телевизионная проблема состоит в том, чтобы выбирать телевизионные шоу на еженедельную телевизионную ночь, чтобы каждый в группе людей видел то, что им нравится.Вам предоставляется список людей (P1, ..., Pn) в группе и список возможных шоу (S1, ..., Sk).Для каждого шоу Si есть подмножество людей, которые хотели бы этот выбор шоу.Вы также получите w, количество недель, в течение которых вы можете выбрать шоу.Вопрос в том, есть ли эти много фильмов, чтобы каждый человек любил хотя бы один из них.

Я не могу понять, какую проблему NP можно свести к этому и как установить сертификат.

Answer 1

Вы можете смоделировать это как Задать проблему с покрытием . У вас есть элементы {P1, ..., Pn} и их k подмножеств T1, ..., Tk, определенных как Ti = {Pj: Pj любит Si}. Затем вы хотите найти наименьшую коллекцию подмножеств, чтобы их объединение было целым набором людей. Решение о том, является ли количество необходимых подмножеств меньше или равно числу, является NP-полным. Поиск фактического оптимального набора подмножеств NP-трудный.